Well, that was easier than I thought it would be. I've got a whole lot more respect for the Apple hardware designers. The metal back of the case isn't epoxied or glued in place, even though it feels completely solid. There are some locking mechanisms between the edge of the metal and the plastic front of the case, and it just pops off with the special tool (and pops back on with some gentle pressure). Very cool design.
The whole process took 20 minutes. 10 minutes of that were spent gently working the back of the iPod case off. I could have done that in maybe 2 minutes, once I'd figured out the trick to it.
The actual battery replacement was completely trivial. No screws, no pins or anything. Just slide the hard drive out, flip the rubber vibration flap out of the way and unplug the old battery. Slap in the new one, and slide everything back into place. Pop the case on and charge it up. The only "hard" part (after getting the case off) was getting the wires that connect the battery to tuck in out of the way - that took maybe 15 seconds of gentle prodding using the supplied case-removal tool.
I took some photos of the process, to show that the ones found online aren't too staged.
I haven't done any battery performance tests yet, but the replacement process was both quick and easy. I was pretty sure I would either bork or scuff my iPod. I was half joking that I'd be ordering a new iPod today - but I'll have to hold off for awhile now... I'll write up a review of the battery once I've got an idea about how it performs - but it will be performing about 15,000% better than what the stock battery had degraded to ;-)
Thanks to FastMac for the battery!