If rkill will not run at all, give exeHelper a try
exeHelper works like Rkill and you can download two format:
Also, please use the guide in http://www.bleepingcomputer.com/virus-removal/remove-malware-defense
There's a method to do before using Rkill. If you've done that, see below:
See if exeHelper will run or if the guide will help. If not, I suggest posting your log in http://www.bleepingcomputer.com/forums/forum22.html
Please mention to them the tools you've tried, including Rkill.