How much does the NAT gateway cost? Quick search didn't turn up anything (and I don't care about this enough to spend more than a few seconds on it). You can turn a regular EC2 instance running Linux into a NAT box by giving it two network interfaces (hell, you can even do it with a single interface) and a few shell commands; I wonder if that's cheaper, even including the price of the public IPv4.

Edit: I see from another post that NAT gateway costs $0.045/hr + $0.045/GB of transfer. That seems... not terrible? An a1.large on EC2 is $0.051/hr + $0.09/GB transfer to the internet (which I assume this type of box would be doing a lot of).