Is it possible to have an EC2 VPC with a public subnet and a private subnet, but without having to have a NAT box? The servers on the private network would not need to talk to the outside world, just to a load balancer on the public network (which also has a private address).
Yes, if the servers in your private subnet really never need to talk to the outside world (they don't download software updates? Don't use public NTP servers?), then you don't need a NAT gateway for them. And the servers in your public subnet don't need a NAT box, they will route through an EC2 Internet gateway.