For about the cost of $50 (U.S.) you could find a P133 or something of the like that will work more than sufficiently as a headless *nix box. Check it out here. There are machines that are available w/ monitors for $50 (U.S.) - shipping is negotiated between seller and buyer, so there is potential that regardless of location you could take advantage of this.
If you are willing to pay for a shell account, I would recommend these guys : http://www.hardlink.net/Services/shells.html
I've never used them, but I've known people that have and have been fairly happy.
Good luck.