Did you have issues when you were using windows 7?
(I'm going to assume you did. If you didn't I suggest you downgrade back to Windows 7.)
Initially when I was reading about your discription of the issues you've been having I would have guessed the PSU.
Random reboots without a blue screen or any type of error message are typically caused by a faulty power supply but not the only possible cause.
BUT... you've replaced that.
Based on the video issues you described I would also have suggested a faulty video card. I've seen similar issues with faulty video cards including my old one. I was getting the "Driver display stopped responding and has recovered" error. After replacing the video card the error stopped occuring.
BUT... you've replaced that.
There are still a few possibilities.
For the random reboots...
1. A faulty motherboard
2. A faulty CPU
For the Error messages and freezing...
1. Faulty RAM
2. Faulty Hard Drive
SO...
What do you do?
1. Figure out if you have a bad RAM module:
http://www.memtest.org/#downiso
(Note: You should run this test [in extended or extensive mode] for a couple of days.)
2. Figure out if you have a bad HDD:
I. Go into your BIOS
II. Turn on your hard drive's SMART feature
(If the drive is faulty it tell you before attempting to boot. If it's not faulty it will boot as normal and you won't even know SMART is enabled.)
3. Fix errors on your HDD:
You should google how to run a "chkdsk /r". -Reason: randomly rebooting your computer causes errors on a HDD these errors can cause many different issues including blue screens and other error messages.
If you are still getting all kinds of errors I would try a different motherboard, which may be the cause of your random reboots as well anyway. Also, If you are having issues with your computer, Windows 8 isn't going to help with anything. Infact it would only make the situation worse. I would install Windows 7. Windows 7 has been out for a while and has a proven record of stability.
Oh, and before you go buying a motherboard remove all extra add-in cards that you don't absolutely need (for testing purposes).
Do the following:
1. Disconnect all Drives except for your windows/boot drive (including CD/DVD drives)
2. Remove all PCI cards like sound cards, wireless add in cards, TV tuners and any other add-in cards you might have.
3. Remove all but the keyboard, mouse, monitor and power plug, plugged into the back of the PC.
Once all of that is removed then boot the PC. It may seem trivial but I've replaced a faulty DVD drive that would not allow a PC turn on. Seems crazy but I know it's true cause I was the tech that fixed the issue. It's also a troubleshooting step used by all major computer companys. (I used to be a DELL warranty service tech.)