I've had good luck with hosting Rails on Dreamhost. They have a good wiki page on how to set it up with capistrano (http://wiki.dreamhost.com/index.php/Capistrano) and you get shell access.