I replaced the battery on my 2nd gen iPod (got mine from www.ipodbattery.com). If you do it yourself, try using guitar picks as the means to pop the case. They won't scratch the metal or plastic parts and they are flexible enough to get in through the small amount of space there is to work with.
It's quite simple. I opened my 3gen iPod quite easily. It's the same as the 4th gen. You can take something liek a .73 mm guitar pick or a SMALL screw driver Then, you put it down on the right side, around 1/4 from the bottom. You'll know when you hit the right spot, it'll pop it out a little. THen once you get the metal part open enough, open the top plastic part, and the rest is easy. Take off the hard drive (carefully) then take the battery out. QUite simple. If you need any pics, or more explaination email me or pm me.
I replaced the battery on my Ipod Mini. The UON battery came complete with tools to make the replacement. The one caveat I would make is to be very careful with two things: 1) be careful when sliding the unit out of the case so you don't scretch the plastic screen; and 2) make sure all of the sliding buttons line up properly. Good luck!