Amazon VPC and using OpenVPN
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