Hey,
I ran into this issue yesterday with a client. However, I was able to get safe mode to work. Your case may be a bit more challenging but we can give it a shot. You're on the right track with malwarebytes and hijackthis. You should also download combofix when the computer finally lets you. Try these steps and report back at your convenience:
1) Try renaming the installation files. For example, mbam-setup.exe --> mbam-setup2.exe. Often times this can help get past the virus blocker.
2) If possible, download portable firefox on a separate computer from here: http://portableapps.com/apps/internet/firefox_portable
- extract it to a folder on your desktop and try using it instead of IE. It may get past some of the blocks that are set in IE.
3) When clicking Google results you'll probably notice it redirects you from all security sites. Try clicking on the "cached" version of the site. There should be a "cached" link underneath each result. Often times the viruses/rootkits don't block access to the cached site.
4) Also, try these lesser known, still reputable, AV on-demand malware removers.
- Hitman: http://www.surfright.nl/en/hitmanpro/
- Prevx (not free): http://www.prevx.com (this was the only program that saved me yesterday.)
It didn't remove every infection but it removed enough for me to finish the cleanup with malwarebytes.
Try those steps and let me know where you get.
Good Luck,
Ben