I would recommend http://uberspace.de/ with their (non root) VPS/shared hosts. Shell-access, Ruby, Python, Perl, node, etc, etc all major DB_Systems, 10gig space, traffic, I believe unlimited. Nerds themselves, that do not wanna have a lot of your data to begin with.
And you pay, what the service is worth to you (minimum 1 € per month).
I switched there some time ago and am totally happy since. Great guys, great service, great philosophy behind the product (and, as the normally do server hosting for smaller companies, financially secured by themselves).
EDIT: By the way: you can try them for one month, just using a untaken uberspace-name without anything else (not even an email-address necessary):