I have been very happy running multiple Clojure web apps using the embedded Jetty server using lein trampoline on a large VPS. I start each app on a different port and use nginx to map to each app to its own domain name. Easy and this lets me also adjust the JVM memory individually for each application. This works so well for me that I almost feel guilty trying alternatives :-)
I don't know if I will permanently change my deployment strategy but I am experimenting using Immutant which is a Clojure deployment platform built on top of JBoss AS 7. After installing the lein Immutant plugin and the latest version of Immutant, then you can run the JBoss AS/Immutant using lein, and separately deploy and un-deploy web applications using lein. Pretty slick, but I am still trying to get a grip on interactive development by connecting nREPL (documentation: Interactive development). My usual style of interactive development is pretty nice (I use IntelliJ to edit, keep the web app running with lein run with live loading of changes to Clojure code (including Hiccup, which is my favorite ""markup""), CSS, etc. I am going to give Immutant with nREPL interactive development a long and patient try - not sure what I will be using a month from now: probably not because I prefer stacks that are less complicated. My days of loving heavy weight J2EE apps are over :-)
BTW, I would bet that many of us have suffered a little using a do-it-yourself custom cartridge on Red Hat's OpenShift PaaS. It works, but at least for me, it was painful even with a lot of useful material on the web describing how to do it. This Immuntant based example looks more promising.
I have used Heroku in the past for Clojure web apps but since I usually have 3 or 4 distinct web apps deployed the cost of about $35 each is much more than putting them all on a large memory multiple core VPS. I very much wish that Heroku had a slightly less expensive paid 1 dyno plan that never gets swapped out when idle, causing a loading request delay.
I haven't yet tried Jelastic hosting. Their minimum paid plan with 128MB RAM (that I assume would always be active, so no loading request delays) is about $15/month which sounds fair enough. They deserve a try in the near future :-)
Another option that I have used for both one of my Clojure web apps and a low traffic web app for a customer is to pre-pay for a micro EC2 instance for a monthly cost of about $5. My only problem with this is that EC2 instances are not so reliable, and I feel like I am better off with a quality VPS hosting company. BTW, if you run a Clojure web app using the embedded Jetty server on a micro EC2, be sure you run it using "nice" to lower its priority and avoid AWS drastically reducing your resources because you use too much CPU time for too long of a period; I find much better continuous performance using "nice" - go figure that one out!
One AWS option I haven't tried yet is using lein-beanstalk which looks good from the documentation. Elastic Load Balancing on AWS costs about $18/month which drives up the cost of a Elastic Beanstalk deployment of a low traffic web app, but I think it does offer resilience to failing EC2s. You are limited to one web app per Elastic Beanstalk deployment, so this is really only a good option for a high traffic app.
A few years ago I also used appengine-magic for hosting on GAE but it bothers me that apps are not easily portable to other deployment platforms, especially converting datastore code. This is too bad because when Google raised prices and brought AppEngine out of beta, that made it more attractive to me, even with some developers complaining of large costs increases. Still, for my desire for a robust and inexpensive hosting for low or medium traffic web sites, AppEngine is in the running by simply setting the minimum number of idle instances to 1 and the maximum number of instances to 1: that should handle modest traffic for about $10/month with (hopefully) no loading request delays.
Edit: someone at my VPS hosting company (RimuHosting) just told me that as long as I set up all my apps, nginx, etc. to automatically start when a system is rebooted, then I probably have no worries: on any hardware problems they restart from a backup on a new physical server. I do occasionally try a soft-reboot of my VPS just to make sure everything gets started properly. I thought that RimuHosting would do this, but I asked to make sure.
Edit: the New York Times has a good article on the big business of offering cloud services that is worth reading: http://www.nytimes.com/2013/03/13/technology/google-takes-on-amazon-and-microsoft-for-cloud-computing-services.html
Edit: 2013-03-14: Jim Crossley set up a demo project that exercises using the common services for Immuntant/JBoss, and wraps project source and resource files for live loading of changes to Clojure code and resources: Immutant demo.