Well, I'm not an expert, but removing the old battery seems like a good idea since once you plug in the motherboard to the PSU it will start trying to charge the leaking battery which sounds like a bad time. From what I could gather you should just be able to connect a new battery to the pins on the motherboard after you determine which pins to use. Sometimes there's a switch to select which battery to use, but the most likely scenario is that they are connected in parallel. A lithium battery should be fine as they are also rechargeable ?
I used to have a 386 25 MHz computer back in the day with a soldered on battery which eventually died, but since the CMOS doesn't reset until you pull the power cord I never actually replaced it. Just didn't seem worth the hassle.