First off, before making any rash decision, consider this.
Is it the 3G giving you problems? Or the AT&T service itself?
I'd contact AT&T to see if they can help you out. Maybe it's the sim card that you are using, or maybe there has been a problem with service in your area.
Next, take the time to set an Apple Genius Bar appointment so they can run a diagnostic on your iPhone. Maybe you just have some faulty hardware, and I'm sure they can replace your iPhone if it's still under warranty.
If all else fails, sorry, there is no chance of them letting you out of a warranty for free. You signed a legally binding contract with AT&T, no exceptions, no questions asked. You'll have to pay the Early Termination Fee if you really want to leave.