Ok, I know about VPN solutions for our internet behind the GFW. But there are situations where this doesn't work for me. Like downloading torrents or keeping an online backup (dropbox was blocked long time ago, why!!!! grrrr).
The logical thing to do is to get shell account on some host somewhere, and use that for everything I can't do locally. I'm quiet comfortable with the linux command line. And for browsing, I go through ssh tunnel. Searching for online shell accounts turns up literally thousands of results, but really I don't need to host a high traffic site with 99.9% uptime. I do need a few GBs (20, maybe ?) of space and a decent traffic limit.

Can anyone recommend a cheap hosting service?

I think the only other solutions are offered by Quantas, Air Asia, Air France, Virgin, United, etc. etc.

It really is frustrating, and now even paid for VPNs are going down it is depressing.

As for the torrents, get UTorrent and set 'Protocol Encryption' to 'Forced' - works like a charm.

Get a VPN that allows you torrents, works very well... easy to find them too, I have seen downstreams of about 600 Kb/s.