The trick is to put the NAT gateway in a subnet that routes through the igw. Don’t put the NAT gateway in the same subnet as the rest of your VMs that route through the NAT gateway, or the NAT will try to route through itself. Create a new subnet that routes through the igw, re-create your NAT GW in *that* subnet, then re-do routing for your VMs so they route through the new NAT GW.
If you need the ELB to also talk to your VMs and route traffic appropriately, you’ll need to put the ELB endpoints (virtual NICs I guess) in the same non-NAT’d subnets.
In ElasticBeanstalk, there is a VPC config screen where you can change around your ELB and EC2 stuff in your VPC, but it doesn’t work very well. I kept getting a “failed reason: ELB cannot be attached to multiple subnets in the same AZ” error when I tried to move my ELB endpoint into a ‘public’ subnet. The problem is that ElasticBeanstalk is buggy. I fixed it by removing all ELB endpoints and EC2 checkboxes except for one subnet, then I re-built the whole ElasticBeanstalk environment. (ElasticBeanstalk has problems (as of Jan 2017 when this article was written) with moving ELB endpoints from subnet to subnet – it left the virtual NICs lying around and then complained when adding a second one in the same AZ – lame). Anyway, building from scratch using the ELB in the ‘public’ and the EC2 in the ‘private’ subnets should get you where you want to be. Make sure that your NAT gateway is also in the ‘public’ subnet and your routes for your ‘private’ subnets route through the NAT gateway.
That should be it. Good luck! Contact me ( @. or @scumola on twitter ) if you have any questions.