IMHO don't bother with shared hosting. It's nothing but hassle; wrong glibc version, wrong postgresql version, wrong some-other-library version, wrong apache/lighttpd/nginx/other-front-end config etc. etc..
VPS is dirt cheap and you get full root
..there are many; the Xen based ones work well with Lisps. Then I'd go straight for a reverse proxy setup (mod_proxy using Apache, Lighttpd or Nginx) -- in particular I'd avoid things like mod_lisp as it is not needed.