If you have a PC you can use this little app I wrote to set your iPhone (not iPod) to a "universal" ID and your iTunes to the same ID. You can then just delete your songs off the iPhone directly from iTunes.
Of course you can already do that yourself by just setting the iPhone to manually sync, something my app does for you, but if you try to do it through the store it will erase your files on the iPhone first.
Here's the link:
Apple & iPhone Forums, Mods, Hacks, News, Themes, Downloads, and more! | ModMyi.com - Downloads - freeSync
It is very beta as I've only used in on my phone and computers but it works great for me.