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.
If you have SSH access, and Python is installed on the system, you don't need root to install Django. The best approach is via pip/virtualenv, but as a last resort, you can just upload the django source folder in the same directory as your manage.py, and it will work.
Look into ep.io, gondor.io, djangozoom.com or one of the other recently-available Django/Python/WSGI hosts, then. They're free to start with (like Heroku) and are built with Django in mind.
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.