You need to look into sysadmin's toolbelt, then. Sysadmins use configuration management systems (CFEngine, for example) for quite long time now. The only thing you need is to put a post-create script (however it is called in AWS), which would install and deploy such system and let the system configure the machine.

I know it's not sexy for developers to take advice from sysadmins, but at the end of the day, it gets the job done reliably and elegantly.