DotCloud looks very promising (Bruno, how'd you get your invite??). I dabbled with AlwaysData for a bit which is a nice free option.
If you are considering it at all, I would highly suggest running a cloud server. It's not as difficult as it may seem and can be quite inexpensive ($10-12/month). I tried Amazon which is fine and am now using RackSpace Cloud. There are scripts and Slices available to get you up and running (I prefer Ubuntu 10.04 distro). I was fairly inexperienced when I started and have managed to get servers up and running without much difficulty.
