Você precisará criar uma segunda sub-rede no seu VPC. Em seguida, você implantaria as instâncias do EC2 que precisam do NAT para essa sub-rede. Eles vão pegar IPs privados dessa sub-rede. Em seguida, crie uma nova tabela Route e associe-a à nova sub-rede. finalmente, ajuste a nova tabela de rotas e adicione uma rota padrão de 0.0.0.0/0 que usa seu NAT Gateway.
O NAT Gateway deve ser implantado em sua sub-rede pública existente para que possa aproveitar o gateway da Internet.
Espero que isso ajude.
Mike.