Alright people. There's this app called Transproxy which seems to be a viable solution to the proxy problem. Now, I am not sure if it will work with all your android phones out there. But from what I've tested, it works just fine. I do my testing on an HTC Desire btw. Like always, I tested it in a network where internet access is through a proxy server, but without authentication. So if someone could check this out on an authentication based proxy network, it would be real helpful!
There's not much to making this work. You just install it and when you run the app, you'll see the above screen. Just enter the details and let it run. It's as simple as that. Even n00bs will find this one easy to work with.:D
Please comment and let me know if this app works for you. If not, well I'll give you some other suggestions.