You can snip the battery out, though it'd be better to desolder it.
As far as hooking up a new battery, use the 4-pin connector directly below the original battery. Remove the jumper, then hook the new battery to the outer two pins... it looks like the inner pin is positive, but I'd take a multimeter and test between each of the two pins and ground to be sure.
As far as what to actually use as a replacement battery, some people have had luck with lithium coin cells (see this thread), just using one of the standard holders with wires soldered to each lead. But, on my board, 3V wasn't enough... I'd just go ahead and use three AAAs in one of these. (Those circuits are usually tolerant of up to 6V, so using 4.5V rather than the original 3.6V shouldn't be a problem.)