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.