How to connect to outside world from amazon vpc?

I have amazon VPC set through wizard as "public only network", so all my instances are in public subnet.

Instances within VPC that have Elastic IP assigned connect to internet without any troubles.

But instances without elastic IP can't connect anywhere.

Internet gateway is present. Route table in aws console looks like

Destination Target 
10.0.0.0/16 local
0.0.0.0/0   igw-nnnnn

and route from inside instance shows

Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
10.0.0.0        *               255.255.255.0   U     0      0        0 eth0
default         10.0.0.1        0.0.0.0         UG    100    0        0 eth0

I tried to open ALL inbound and outbound traffic to 0.0.0.0/0 in security group that an instance belongs to. Still no success.

~$ ping google.com
PING google.com (74.125.224.36) 56(84) bytes of data.
^C
--- google.com ping statistics ---
6 packets transmitted, 0 received, 100% packet loss, time 5017ms

What else can I do?

It appears that the only way to get outside from instances that don't have Elastic IP is:

• Create a NAT Gateway or NAT instance
  • Must be public with an Elastic IP assigned
  • NAT Gateways are a newer solution, are recommended by AWS, and are fully-managed (low maintenance).
  • NAT instances are an older way, are not recommended by AWS, but are available as a self-managed option that gives you full control. You can launch an extra m1.small instance from ami-vpc-nat-beta
• Create an extra subnet which will be "private"
• Move non-EIP-instances to that private subnet
• Modify route tables: 0.0.0.0/0 from the private subnet should go to NAT

So, just adding NAT is not enough. Instances should be stopped and moved to another IP from another subnet.