Recommend Me A Webhost!

Folks,

I am looking for a free or a paid webhost that will allow me to run my own web proxy for the public to use. I am not looking to use a third party service. No! I want to provide the proxy service to the public (like to you) like anonymouse.org does.

I’m going to use Mini Proxy php script to run the service. And, I’ve searched google twice before few wks ago on 2 different days but no luck. The webhosts I usually find, will not allow me to run my own public proxy service. Some will not allow me to run it on a shared server and expect me to hire a dedicated server and charge me an arm & leg every month. That’s the big problem.
I’ve used many keywords in the google search to find the right host. But, no luck. Can you think of a few key-phrases that will yield positive results on the google search ?
The host must allow me to use port 3306 so that my .exe bots can dump data to my website’s mysql database.