Grooveshark already does everything listed. And it's been available in the USA for years. The only problem is their iPhone app has been continuously rejected by Apple so they've been forced to publish for iOS on Cydia's store for jailbroken apps. That and licensing/litigation issues with some large recording companies. They have deals with a few and have been through court with others.
Grooveshark is user uploaded which means duplicates, fakes, bad tagging (so the "same" song might have widely different total times). Use Grooveshark if you like trial/error in your music listening.
Another upside to user uploaded content is that Grooveshark has a massive library of available songs. I have found the most obscure artists in different languages on Grooveshark. I listen to a lot of music and artists and there are very few musicians I haven't found on Grooveshark.