Before I begin, these guys haven't paid me for this endorsement and there are no tricky affiliate links here. Just good old fashion link recommendation.
I came across some inexpensive "advanced" hosting from railsplayground.com during one of my random web sessions. You can find them here.
"RailsPlayground.com Ruby On Rails Hosting":http://railsplayground.com
I say they are advanced hosting because they offer a stack of stuff that "power" users require. E.g. SSH access, subdomains, CVS/SVN, FastCGI, *ruby*, unlimited db's, php 4 and 5!
All that starting at *$24 a year*!
I'm blogging about this because when I was looking for hosting I found it really hard to find this type of service. My only concern with going with this company is their reliability as they don't talk of redundancy, backups, etc which sets off warning bells in my mind. Also, who knows how many users they are throwing on each box? Still, it may be suitable for your situation. Let me know how you go if you do happen to go through this company.
You may also like to check out "Web Strike Solutions":http://webstrikesolutions.com who are only $30 for your first year then $84 each year after that but do not offer power hosting features like SSH, CVS/SVN, etc. They seem quite professional. I've been through them in the past and they were fine.