I found it easier to use the big blue opening tool to do what you normally shouldn't do and enter the device from the (empty) sd card slot, pulling the case upwards by carefully using the prying tool as a lever at that point. One of the nearby tabs will pop open and you can slide a prying tool around the upper side of the player. It's hard to work from there to get around the corners; I've only had success by inserting multiple prying tools nearby, forcing the case up until I was able to press one into the tiny opening around the corner where it released one of the side tabs. Same procedure as before and you'll be able to work around the lower side.
In my opinion it's almost impossible to not damage the case which shouldn't be an issue anyway if you bought the rubber protection "sleeve" back in the day.
+1 for the black spudger, glad I had it. It's also comes very handy to work on the connectors; much better suited for that job than the blue prying tools... I'm also not feeling too good about how the old battery bent during removal.
To others as it seems these steps are consulted for other repairs: If you don't intend to replace the battery, leave it in if you can, just disconnect it. Removal appears to be a pretty destructive process; at least I wouldn't want to use the old battery again.
Just in case you've never opened such a compact, tightly snapped device before (such as me): Just attempt to insert and _slide_ prying tools and an old plastic card around the case for a few times, it appears the case will eventually separate more or less "on it's own" if you keep doing this. Attempting to visibly PULL the case off edge by edge does NOT help (I just spent almost an hour to figure out that attempting to use the tools like a crow bar does not yield any viable result despite looking good at start). Apart from unnecessarily warping the case, attempting to pull the case off may also result in the case getting stuck on the power button - you want to avoid that...
Also check that all button "pins" are still there when the case separates; for me the power button "pin" (the external plastic springy bar) came loose and needed to be reattached.