I worked with AWS a little while ago. I'm not sure what options there were, but I recall setting up my on node and (Linux) OS. You then install what you need (aka Pyramid) and run the service from a node within the Amazon cloud. Be careful about what happens on reboot and what might get lost -- not sure if you need Amazon S3 storage as well. You can start with their minimal package for free to try it out, but don't expect much performance out of it -- it is only for developers/trial users since it is free. (At least it was at the time)
BTW other services like Linode seemed at the time to be much better and cheaper.
Google App Engine is another option; it comes with some limitations but ones that are understandable if you understand the concept of GAE. I have found if I rethink my app to fit GAE, I have a cleaner solution anyway.
Hope this help and isn't TMI.
-John