Since he is on a shoe string budget, there are plenty of cheaper VPS solutions, many under $7/mo. I had one for $3.84/mo for awhile. Latest deals are collected at http://lowendbox.com
Be sure to push your DNS through the OpenSSH tunnel too, or they'll see your client's DNS requests. Here is a very short write-up on safe web browsing while on untrusted networks: http://16systems.com/OpenBSD/untrusted.pdf
Instead of an OpenSSH tunnel, use OpenVPN. It has settings to automatically push DNS, and on my Mac for example using Tunnelblick (a wrapper) I can have a GUI that can give me status updates on my tunnels, and when they get disconnected, to make sure I don't accidentally sent information down the wrong line.
For proxied services, the proxy (e.g., squid) server on the other end of the ssh tunnel will be making the DNS requests.
If you want to be fastidious enough to hide the DNS for un-proxied services, you'll probably also want to have a firewall blocking and logging most outgoing non-tunneled services so you can identify them and configure the clients and proxy appropriately.
The problem with this is the same as for services like dropbox. If enough people do this they will start blocking the slicehost IPs.
To be successful you need to have
* IP usage distributed over a wide range
* private distribution of proxy details
* ability to switch to a new proxy when your current one is blocked
Tor tries to accomplish most of this, but from the OP's post it appears that it is being effectively blocked, either by watching Tor entry points or by packet inspection.
In practice, only services that are advertising themselves as a way to get around the firewall may get blocked. Using SSH through some arbitrary VPS provider in the U.S., the chances of it getting blocked are very low...low, as in I've done it for years with the same IP with no problems.
In practice the great firewall is still not blocking vpn, even a weak pptp is ok.
Many very well known vpn services are still not blocked, and not because of ignorance from govt. Just search for vpn on taobao (chinese ebay), and you'll find plenty of options.
Tor encrypts between nodes, the problem is getting connected to the Tor network, you need an entry point. What the government is doing is blocking the entry points. Initially the public bridges, and then the bridge nodes (normal ones anyway).
You need to get the ip of a bridge before you can connect, but once this becomes available(semi public information) the government also learns it and blocks the ip.
There are dedicated teams here whose job is to suppress connections to Tor from inside China.
Edit: just saw two others recommended this approach.