My electronics skills are pretty much limited to upgrading my PC, so I was fully expecting to brick my iPhone in the process. Once you actually open it up though, everything slots in very nicely and obviously. The only tricky bit was keeping track of the different sized mini-screws and making sure I put them back in the right place.

I followed an ifixit.com guide (like this: http://www.ifixit.com/Guide/Replacing+iPhone+3GS+Battery/154...) which, combined with the video, was very easy to follow.

Alternatively, you could probably find somewhere to do it for you for maybe $50 or so (still cheaper than Apple), but I doubt they'd use anything more than the cheap stuff you find on Amazon.

Still, it's worth following the other suggestions first and seeing if you can downgrade the iOS version.