No icons, no Start menu, no safe mode!

Hello,
For about a week my computer at work has been loading without icons or a start menu. I have read through the forum and have tried everything I can to get it back up again and nothing works. When I start in safe mode the screen is completely black except for the text in each corner reading "safe mode". I can access the internet via the Task Manager and even Office, pictures, etc. I can not access control panel or anything similar. I have tried to type in "explorer.exe" to the New Task (Run) bar and it comes up with "file not found". I have tried typing "msconfig" and doing a total system restore, still nothing. I have downloaded Miscrosoft Malicious Software Removal Tool and it removed a worm and two Trojan Downloaders, I then did the restore and downloaded the newest Explorer and still nothing. I tried the other way around, Removal tool, download Explorer then reboot. Nothing. Last week I downloaded AVG free and I updated to Windows XP 8, I thought one of those may be the problem but I can not get into control panel to remove AVG. I have tried from "RUN: windows, program files, AVG" but there is no uninstall. I have read several forums and different things seem to help different people but none of them have helped me! If anyone can help I would be ever indebted. The computer is an NEC Powermate and the montor is a Flatron LG. I do have problems with the monitor but I don't think it's related as I have always had this problem. Computer is also second hand from and office environment.
Hope that's enough info!
Thanks