Computer hangs at BIOS screen. Cannot enter setup

After the edit, it sounds like a device enumeration issue, something wrong with the hard drive probably. If you try swapping it out for another hard drive you know functions well elsewhere does it again stall?

Original reply:

If it hangs at POST it probably indicates a defect with a critical component (ie. not a component like the hard drive, but a component like the memory/mainboard/CPU). It sounds like you've done everything you can to try and alleviate simple issues with CMOS corruption/bad seating, so I would suggest there is an actual defect on the mainboard or a problem with device enumeration, there nothing to speculate any further than that.

Hope you get it fixed.

Sounds like a device isn't being detected properly and it's hanging trying to enumerate it. Probably, if you wait long enough (potentially 30+ minutes) it may eventually go past. That said, since you unplugged the hard drive and it quit, it's almost certainly the hard drive. It could well be a motherboard fault or something but it's unlikely. The easiest test, of course, is to try another drive or try this drive in another machine (although note, other machines may be more lenient about their timeouts)