Hostgator shared accounts actually do have shell access, you just have to ask for it. Go into the live chat and ask a rep and they'll activate it for ya.
They also have cheap dedicated servers called "unmanaged servers", they're kind of an unpublicized deal, its $75/mo for your own box, which I think has a 2.4 P4 and 1gb RAM, 5 IPs.