Replacing CR2032 batteries for battery-save games.

Okay...I've got a Super Mario All-Stars & Super Mario World cartridge with a dead battery. I opened it up, and it uses a standard CR2032 button-cell battery. Easy enough to find. The problem is, the damn thing is welded onto the battery clips! Even a soldering iron wouldn't loosen them. Has anyone ever successfully replaced a battery in a cartridge before?
Yes but it was a pirate cart (hence it used phillips screws instead of game-bits, I need to get a set of game bits still).

You can trace the last solder point the lines for the battery clips go to and just solder in your own new CR2032 socket cutting the traces that went to the old battery. Sockets cost about $1.50.

Soldering to a battery just scares me.