You might want to look into a VPS. It costs more money than a standard hosting account, but you do have root access to do whatever you want with it.

I've been using these guys for a couple of years now, and am pretty happy with them.

http://www.servint.com

Edit: deleted a massive amount of useless, Microsoftian bottom-quoting -wfaulk