would be to restore from your backup....
However if you don't have that option then recovey from iPod would at least get the dat there and then you just need to rebuild the Metadata I lost all of mine when it changed from Rythmbox to banshee and since then have used a cloud (dropbox) to keep my banshee database. This gives a couple of benefits, I have 1 x cloud vesion and several backups and all my computers, including smartphones are in sync.
Genrally recovery software will only bring some info back so manual intervention (will always be_) is usually required. Howver if you truely lost the lot then you probably have bigger HDD problems (do you have SMART info to look at?) and before you invest in data recovery and manual time and effort I suggest you check the HDD out, replace if necessary, and consider a simple backup policy for critical data.