1) If I create an Instance in a "public" subnet, it can only access
the Internet if it has an Elastic IP address associated with it.  Is
there any way to allow a "public" subnet to access outbound Internet
like a non VPC Instance can, without Elastic IP addresses?

I need outbound internet access to run system updates such as yum, and
communicate with required external 3rd party services.

I tried playing around with a "private" subnet which uses a NAT router
instance, which works for most of our backend/internal servers, but
then you run into two problems: a) routing doesn't seem to work for
Elastic IP assigned addresses in the NATed subnet and b) the load
balancer doesn't appear to work with NATed subnets (which is a problem
for #2).

Elastic IP addresses would seem to help with the "public" subnet, but
with a limit of 5, after you add a NAT, Load Balancer and soon to be
OpenVPN instance my limit is nearly exhausted, which leaves nothing
left for the actual web instances.

2) Which leads to the primary issue - Load Balancer.  If I point the
load balancer to instances in the "public" subnet, they work fine, as
far as load balancer routing and web access, but these instances are
unable to communicate with the external 3rd party online services.
(and I do not have sufficient remaining Elastic IP addresses to cover
these instances for "public" internet access).

If I point the load balancers to instances in the "private" subnet,
where the instances can communicate with the external 3rd party
services fine, it breaks the load balancer's routing back to my client
browser.

I just can't seem to find a combination that will work for this setup.

Thoughts?  Suggestions?

What load balancer are you using? We used ELB and only wanted those
instances accessible, so only our ELBs were in the public subnet. Our web,
database, and utility boxes were all in the private subnet(s). We used the
NAT router for all private to external connections. Because ELBs get a
public IP by default it all worked out.

We did have one other server in our public subnet: a SSL bastion that we
could connect to and then connect to the private boxes. So because of our
use of ELB we only needed ElasticIPs for the bastion and the NAT.