Bem, você praticamente listou todas as opções disponíveis, pois eu vejo que você terá que escolher uma das suas duas primeiras opções se quiser aproveitar os ótimos recursos oferecidos pela AWS (como como balanceamento de carga elástica e dimensionamento automático).
A coisa NAT que você mencionou provavelmente seria algum tipo de proxy reverso (?), mas você encontra o mesmo problema lá. Você quer que a camada de proxy seja redimensionada automaticamente também, mas você não poderá alcançá-la, pois precisará de IPs estáticos (... e estará de volta à estaca zero).
Eu mesmo tenho lidado com esses problemas, e sempre acabei configurando uma zona hospedada no Route53 e alterando os servidores de nomes no nível de registrador para apontar contra ele.