The Internet Archive has a large collection of netlabels: assorted music released under a Creative Commons license. (In other words, it's generally ok to use it as long as you give credit to the artist.) Their open-source audio project is also notable, although you'll have to sift through the audiobooks and other non-music.
None of this is mainstream music, except (of course) for the Grateful Dead... not sure if this is a concern.
There is no API, but the Archive's interface is insanely simple: no Flash, no JavaScript. You could probably write your own song-retrieving process without much trouble.
...of course, this will scale like ass. If you have a small userbase, you might give it some thought.