My webhost has SSH access, it just doesn't give me root. It offers RoR through CPanel, which I just assumed would work, but I haven't tried using it so I don't really know.
But I take your point, a VPS is really the best thing. I just can't convince my husband to let me spend money on it and I'm unemployed :P.