A bad CPU fan is only part of the overheating problem. There are a variety issues that can cause overheating forced shutdown.
Bad/underspec PSU is also a problem that can cause shutdowns. If the voltage supplied by the PSU is unstable, the system will be unstable or 'protection' features kick in and shutdown the computer. If the system draw is more than what the PSU can handle or the PSU is overheating, the PSU's protection circuits will shut the unit down.
Sounds like hardware to me, though there are many issues that could cause random shutdowns, any one of the components connected to your computer could be causing it. You mentioned 4 beeps, without knowing what kind of bios you have (it'll be visible when you first power up Examples such as AMI, Award, etc...) and the sequence of beeps (which ones are short and which ones are long) It's tough to know exactly what your computer is complaining about.