Start from Scratch
If you have a recent database and files copy nuke all and start all over again. This is truly the best way there is when you have been hacked in a massive way.
No Good Backups
Most of the time there is no good backup in my experience. And I guess you do not either. If you did a scan with ClamAV and or online scans with sites like
and found the contaminated files you could remove and or replace them by clean files. Hopefully all hidden shells will be caught as well as all other possible backdoors. It does seem like the infection is pretty bad though. So hard to say this will be waterproof. It has worked for me before so do try!
Backdoor Shell
In your case it seems there is probably a Shell file on your server you missed with a name the scans do not find easily. Online shells are files that have server rights to change other files on that server on command. Shells can have names like "I love you" or other less taunting names. I have found several in the past and have some on backup to use as intel in case I need to help another client.
Compare clean install to contaminated one
You could also do a comparison using Diff or Meld - GUI version of Diff - and compare a clean installation to the infected one. This will cover all standard files, but not the template nor extension files. These you would have to do separately using the proper packages.
Database Cleanup
This all will not help with the database as much though. If you have a copy of the database that is OK and was from before the hack I would replace the database by that copy. If you have a decent backup of all files and the database a clean start would be the best way anyways. If not, then I would use some of the upcoming command line tools if possible. Remember you can download a database copy and run these commands locally as well!
Command Line Tools
Another option - if you have Shell access - is to do some basic scans for obfuscated code. There are even some PHP scripts I use for that that work as well. Here some useful search and destroy stuff. Most of them help to unhide obfuscated code like:
<?php $_8b7b="\x63\x72\x65\x61\x74\x65\x5f\x66\x75\x6e\x63\x74\x69\x6f\x6e";$_8b7b1f="\x62\x61\x73\x65\x36\x34\x5f\x64\x65\x63\x6
PHP Script(s)