Acho que você está descrevendo o Amazon VPC (Virtual Private Cloud). Esse serviço da Amazon permitirá que você atinja sua meta de acessar com segurança suas máquinas virtuais sem IPs públicos, estabelecendo um túnel VPN IPsec. Esta solução funciona melhor quando você tem um IP estático, ou então você pode ter que reconstruir o túnel quando o seu IP mudar. O campo de vendas da Amazon está aqui: link
Eu usei com sucesso firewalls do pfSense para estabelecer túneis usando o roteamento estático e o BGP.