Em suma, AWS + Cloudformation + Ansible (ou algum outro software CM).
Com o cloudformation, você pode definir sua infraestrutura de "porcas e parafusos" - redes, servidores, instâncias do RDS, etc., e implantar essa infraestrutura de maneira confiável e repetível. Esse mesmo manifesto de cloudformation seria implantado uma vez para cada cliente.
Uma vez que a infra-estrutura é implantada, use um sistema de gerenciamento de configuração para configurar seus servidores, implantar código, etc. Ansible é o que estamos usando, e descobri que está acima da concorrência (Puppet, Chef , Saltstach, etc.), tanto quanto facilidade de uso e flexibilidade. Ansible é um projeto python, e sendo uma loja python, seria fácil para você se atualizar.
Além disso, considere ver se você pode implantar seu aplicativo usando o Elastic Beanstalk da AWS. Se isso for possível, você terá que lidar com a implantação, as atualizações do servidor e o dimensionamento.
Se você estiver preocupado em manter uma proporção de 1: 1 de clientes para instâncias de servidor, considere a implantação de várias instâncias do seu aplicativo em um único servidor usando o Docker. Isso permitiria uma quantidade razoável de segregação entre as instâncias do aplicativo e, ao mesmo tempo, tornaria mais fácil implantá-lo de maneira controlada.