I also found
another tutorial which would have let me get this working on Vultur for $2.50/month, which isn't free, but is manageable. The reason I wanted to get Kali was so I could install packages like amass which aren't in Debian.
But it turns out: you don't actually need Kali for a lot of these packages. You just need Debian and pointers to the Kali apt server. Here are
instructions on how to do that. So in the end, I gave up on installing a full version of Kali on AWS or GCE and went this route. I'm just using a stock Debian AMI on a Free Tier Amazon t3.micro instance. Since I don't need heavy-duty network analysis or GUI things, I'm hoping that this will be enough. Everything is working so far.