Because of some unfortunate circumstances I noticed I irrevertibly mixed up my sorted and retagged mp3s with an old backup. That means now I have files that are basically duplicates except for the id3 tags and paths. FSlint does a nice job of finding real duplicates, but is there any free tool to detect duplicate mp3s that differ in their ID3s? My preference is a linux tool, but windows would be acceptable, too.
EasyTAG can do this all and more easily. Most importantly for your purposes, it allows you to define and use a naming scheme based on the ID3 tags.
Edit: After rereading the question, this isn't exactly what you wanted. However, after renaming the files, you can use FSlint to delete the duplicates.
DupeGuru does a nice job comparing tags or also only the audio content.
DuMP3 claims even more features but I didn't spend enough effort to get it running (32 bit SWT on 64 bit linux...)
DupeMusicMatch might also help, but I didn't try that yet.