Deactivate all of your plugins. In fact, write them all down on a sheet of paper and delete them. Hackers may try to insert PHP code in your plugins that, when run, re-insert the malicious code that you are about to remove.
Hackers like to inject code in your database, particularly the options table. Go back to the Plugins section and search for the Database Reset plugin. Install the plugin and it should be the only active one right now. Go to Tools > Database Reset. Under Select Table, pick options. Type in the generated captcha and click Reset Database. This resets your Options table as if you just installed a new blog. Don’t worry, you will get everything back later on.
Install a new theme that isn’t yet in your Manage Themes tab. Theme files are just as prone to attacks as plugins. Temporarily using a new one will assure us that you are wiping the slate clean. If you wish to stick to your old theme, you must re-download it from a trusted source and re-install.
Head to the Users section and check if there are suspicious names in your list of users, admin users in particular. If there are, delete them. To be safe, change your password as well.
5. Installation Files
These files are your core WordPress files. To be sure that the hack is fully removed, re-install WordPress. To do this, go to your Dashboard and click Updates. To re-install, click the Re-install Now button. Go back and visit your blog if you still see a warning. If not, congratulations!
6. Picking Up the Pieces
Go over your list of plugins and assess which ones you absolutely could not live without and the ones you could do away with. More often than not, many of these plugins were installed a long time ago and have not been updated, thus opening the doors for hackers to use them against you. I’m not saying the plugins are the main culprit. It’s just wise to use plugins that are easy to manage and actually benefit you. It saves you time, not to mention bandwidth! Once you have decided on which plugins to install, go to Plugins and bring them back one by one.
Like I said in #3, you have to download your theme from its original source and re-install it if you haven’t already done so. As much as possible, get it only from the WordPress theme database or from the site of its author.
Read up on Hardening WordPress. It suggests ways to protect your blog from future attacks.
Since we reset your options table in Step #2, go to Settings and browse through its subsections to see if anything needs to be changed, specifically your blog title or description, discussion settings and permalink structure.
If your blog has been blocked by Google, you may request a malware review by adding your site to their Webmaster Central service, under Diagnostics > Malware.
Feel free to leave a comment or suggest methods of recovery that I could add to this post. Thanks!