I'm not interested in having all of my EC2 instances having a public IP on their network interface. I want to have full access over what boxes can speak directly to the Internet and which can be reached directly from the Internet. In a typical, very basic setup, you'd have a firewall on your DMZ with something like OpenVPN running on it so clients can get on your "internal" network and work with machines on your private LAN (RFC1918 IP space). My question is, it looks like Amazon VPC currently only caters to IPSec hardware VPN solutions. Is there anyway I can setup Amazon VPC and use a software VPN so my colleagues and I can login to our cluster of EC2 servers behind a VPN? I don't want to have slap on public IP addresses on any of the machines. The load balancer will eventually be on the DMZ and speak to the boxes behind the VPN/Firewall. What's the best way of doing this on Amazon VPC?
VPC is exactly what you want. You can create a VPC with a public subnet and a private subnet and put the OpenVPN server on the public subnet. There are OpenVPN AMIs already setup to do this. see http://www.openvpn.net/index.php?option=com_content&id=493 and http://www.openvpn.net/index.php/access-server/docs/admin-guides/499-openvpn-access-server-ami.html
You can easily do it with openvpn. I followed the following posting and it worked great
http://sysextra.blogspot.com/2011/01/creating-virtual-private-cluster-with.html
OpenVPN runs fine on the Ubuntu EC2 instances we've set up. I'm not sure about the details of VPC, but if you can get one (or more) EC2 instance connected by VPN you should be able to do something and route through that connection.