can't boot in safe mode; can't install antivirus

HI GUYS. I badly need help. My PC is acting weird. The symptoms are enumerated below. Suggestions are very much welcome. I found a similar thread with almost the exact symptoms. The guy found a solution. I am really hope I'll find mine. Please do take time to read my post.


SYMPTOMS:
I first found out about the infection about two days after the internet connection at home was restored.(My provider had a routine maintenance check up for the lines in my neighborhood.) I can't really say when is the exact date of the attack. So here is a list of symptoms of the infection/attack?.

1. McAfee anti virus stopped working.

2. Can't install anti virus. Tried to install other anti virus. The list includes AVG, Kaspersky, and Nod 32 but all failed.

3. The IE and opera browsers does not work but firefox is fine.

4. Can't connect to Yahoo! Messenger. Prompts a message telling to try again. Every time I do, it prompts the message again.

5. Can't boot in safe mode. When I try to boot in safe mode, it loads all the drivers and reboots again. Normal mode is fine.



WHAT I TRIED TO DO:

Note: Since my pc is sooooooooo slow, I reformatted my pc hoping the problem would go away. Unfortunately, it didn't do anything good with regards to the infection. It did make my pc a little bit faster though. Also, I can now use the opera and ie. Still, the problems persist.


1. Installed SuperAntiSpyware. Scanned pc and detected infections. The Log is attached in this post.

2. Installed Spybot successfully ( I think). However, I can't open the program. When I try to double click the icon in the desktop, nothing happens.

3. Installed Malwarebytes. Scanned pc. For a while it worked but prompted the message:

An error occurred. Please report the following error to the Malwarebytes Anti-Malware support team.
Error code: 731(0,9)

QUESTIONS:

1. Is it OK for my PC to be connected in the internet while cleaning?

2. After my PC is cleaned, I am planning to use deep freeze to protect it. Any of you guys have a opinion on my plan?