How to connect to outside world from amazon vpc?

Or create a NAT Instance within the public VPC and add a static route to that NAT instance

route add -net 0.0.0.0 netmask 0.0.0.0 gw 10.0.0.5 eth0

where 10.0.0.5 is your nat instance, just make sure your the security group which contains the NAT instance can accept internal traffic from the boxes you require internet access

The docs tell you should add a NAT Instance

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

• add a NAT (Launch an extra m1.small instance from ami-vpc-nat-beta) and assign EIP to it
• 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.

Q. How do instances without EIPs access the Internet?

Instances without EIPs can access the Internet in one of two ways Instances without EIPs can route their traffic through a NAT instance to access the Internet. These instances use the EIP of the NAT instance to traverse the Internet. The NAT instance allows outbound communication but doesn’t enable machines on the Internet to initiate a connection to the privately addressed machines using NAT, and

http://aws.amazon.com/vpc/faqs/

You can find detailed instructions on how to setup a nat instance here: http://docs.aws.amazon.com/AmazonVPC/latest/UserGuide/VPC_NAT_Instance.html