The thing is that batteries in first generation DMG games are virtually all going dead now.
I have two copies of Tetris with what I think are dead batteries, but I took them apart to look and they don't have visible batteries, just a conspicuous epoxy blob on the PCB… maybe the save RAM in them is powered by a capacitor?
My point is, a lot of those games have dead batteries now. Which is strange, my copy of Pokémon Red is fine in the battery department.
As for the actual procedure, it's fairly simple, yet it's not for beginners. If you overheat the battery, it will explode and spray acid.
If you're not already competent at soldering, I'd ask a friend to help or to do it for you.
To actually do it, you need the 3.8mm security bit to open the game cartridge, as well as a replacement battery. Different games are sized for different batteries on the PCB, so check before you go looking for a battery. The batteries are stuck to the board with solder tabs, so you'll want a replacement with solder tabs as well. This same shop I'm linking to also offers a battery replacement mail-in service, but I don't know if the added cost is something you can justify.
Anyway, in short, if you already own soldering and desoldering tools and know how to use them, the battery change is as simple as finding the battery and making two quick solders. If you don't have tools or know how to use them, the procedure is as simple as finding the battery and a friend with tools who can help.