I was faced with a fakealert virus yesterday that existed in safe mode also, which made cleaning it very difficult. I used the command prompt method I used a couple weeks ago to clean it. Luckily, I was on a network - not sure I would have been able to do this on a stand alone computer. Here were my steps:
[on the virus affected machine]
boot into safe mode with networking
log in as a domain admin
create new local administrator (on the chance that I didn't know the local admin password)
[from another machine in the network that is not infected]
from another machine on the network logged in as a domain admin
go to \\10.0.0.54\c$ (affected computer drive)
create a new folder on the root of C called malware
download newest version of combofix and copy it to \\10.0.0.54\c$\malware
[on the virus affected machine]
reboot into safe mode with command prompt
log in as local administrator
run c:\malware\combofix.exe
You won't be able to install the recovery console, but in the two times I've tried this, it hasn't been a problem.