Alright... The BIOS battery is a 2032 button cell on the motherboard. Most of the times it's sitting flat, on some motherboards it's sideways. In any case it should pop off without violence. There's a spring in the slot, pushing towards it usually does the trick. Note that your settings will be reset. Usually setting to optimal defaults at the BIOS "save" screen are good. Also, at least when you get back to Windows, your time and date will be way off and need to be set correctly for many functions to work properly.
If it's a heat issue caused by a failed cooler, it's instant. It takes a second or two for the CPU to reach its maximum temperature no matter how long you have had your system unpowered.
The best air cooler is made by Noctua but there's a lot of decent ones from other makers, too. Look for airflow versus dB. However, if you aren't going to overclock, basically anything will work. Even the factory coolers are efficient enough and if you're lucky you can get one for next to free. As I understand your rig isn't of the latest fashion, so it's useless to pay big money for the cooler in any case. My Intel e8500 from 2008 overclocks nicely with a $40 cooler. Air cooling is much more fail safe than liquid. If the fan stops whirling, that's visible and easy to fix. With liquid it's either a loss of liquid, blocked circulation, failing fan...
After all this being said, it still can be a PSU issue or a combination of one or several other factors - some of which may be caused by the failing PSU. Because of the fast spinning fans I still vote for insufficient cooling, which also is the easiest and cheapest to replace for testing.