Some common points I see throughout this thread.
You can not 'upgrade' to a new version once your site has been hacked. The 'upgrade' is unlikely to remove all (or any) of the hack and the newly 'upgraded' site will just be hacked again.
Solution:
Delete all files within your public_html directory and follow the security checklist 7 info. Download fresh files and upload the fresh files to the site. Then do the 'upgrade' to a new version.
You can not just 'overwrite' your sites files with fresh ones. This may not remove the hack if the hack is in it;s own directory and/or has additional files uploaded to your site. This is very likely with certain hacks. Again, this will simply cause your site to continue to be hacked.
Solution:
Delete all files within your public_html directory and follow the security checklist 7 info. Download fresh files and upload the fresh files to the site. This will eliminate any added directories and added files that would not be replaced by coping over the Joomla files with new fresh files. Be aware as mandville mentioned above that C-panel will generally create blank htaccess file in public_html if it does not find one there so do not be alarmed about this file suddenly appearing.
You can not trust your site file backups as these backups may be contaminated with the hack files. By using backups you may be simply putting back the hack and in essence infecting your own site again and again.
Solution:
Delete all files within your public_html directory and follow the security checklist 7 info. Download fresh files and upload the fresh files to the site. Then do the 'upgrade' to a new version if your not on the current version of your Joomla series. Consider migrating or moving to the 2.5.x version.
Do not fully trust your database. This is where the bulk of your Joomla information lives, and is normally kept for reuse. Though this is still rather rare, it has been seen that code can be added to actual article text contained within the database which will execute when the article is displayed on the site. This is similar to a template hack; just using a different method.
Solution;
Reuse the existing database, but check (offline with a local development server setup xampp, wampp etc. if possible) the database articles for any added code. Use the sorcecode viewer in your desired Joomla editor to do the inspection, or copy the article sourcecode to Dreamweaver or a text editor (Notepad++) and look for anything strange there. Also sort your Joomla users by group and make sure any who have backend (admin, super-admin) privileges are actually people you gave the privileges to.
Do not trust your host especially when using a shared hosting or vps account. Many, big and small, have a high incidence of hacked servers as evidenced by these forums and Google. Ever wonder why?
Solution:
If you suspect your host is not serious about security setups, keeping the server malware free, and the server software up to date, or their tech support appears to be reading off que cards, then find a better host. Cheap does not necessarily mean bad and expensive does not necessarily mean good. Web Hosting Talk is a good place to find decent hosts.
The above is not exhaustive and you should make sure you at least follow what is written in the checklist 7, It is also wise to head what is in the "Before you Post" forum sticky
http://forum.joomla.org/viewtopic.php?f=621&t=582854 The documentation is there to assist in properly fixing a hacked site and helping to prevent it from happening again.