FWIW, I was going to mention VPS as an option, but it sounded like
*maybe* you'd been working under a managed hosting environment, so
Heroku seemed like a natural fit to your question (easy Rails installs
with support for a wide variety of libraries/common dependencies),
which is why I mentioned at least looking into it.

That being said, a VPS like Slicehost would grant you pretty much free
range to do whatever you like with the proviso that you'd be managing
the whole she-bang and would need to keep your whole LAMP stack
updated/patched yourself. As a Ruby newb/fiddler, after looking for a
play space to run some of my own Rails projects, I opted for Linode, a
somewhat new competitor to Slicehost.  But both seem like pretty good
options to me.

Of course, there are a mind boggling array of other options, including
managed VPS's - more restrictive, but there are some that seem more
willing to accommodate your needs than others. A good friend uses
WiredTree out of Chicago for all of their commercial Drupal sites and
love the support they've gotten: http://www.wiredtree.com/. It looks
like they do support Rails, but I have no idea how well:
http://www.wiredtree.com/managedservers/software.php.

Anyway, good luck.