iPhone 4 won't connect to the internet except on wifi
You have done many of the quick fixes, but the best guideline on troubleshooting this would be to re-start the troubleshooting process:


http://support.apple.com/kb/TS3780


Before you start, do you have a backup of your device?

Also, you can test the data connection with some very simple items to rule out Mobile Safari or other items being blocked.


Go to Settings App - turn off Wi-Fi
Go to Settings -> General -> Date &amp; Time and turn off "Set Automatically" and then intentionally set the clock back 10 minutes in the past.
Turn off the phone.
Turn on the phone - verifying WiFi is still off and the date is still set incorrectly and in the past.
Go to Date &amp; Time and turn on "Set Automatically" and see if the date can be set from AT&amp;T's network connection.


At that point, I would then go through the steps in the above article, noting on a piece of paper what results you get. That way should you need to contact AT&amp;T or Apple - they can't give you the run around. It is Apple's responsibility to explain how to test the device up to and including restore / erase and setting it up new. It's AT&amp;T's responsibility to ensure your data service is working if you are paying for it. You can not give them an easy out if you document your efforts to solve it and have done all the things that are expected of the end user.

Hopefully something simple like a power cycle and eliminating the WiFi will allow the cellular data to start working again, but it still could be something out of your control and you'll need help from Apple or AT&amp;T to finally solve it.