Is there any site for free music downloads that is NOT illegal?

none of the sites are illegal. it’s the actual sharing of copyrighted music that is.
but. . .

As far as I know, sharing copyrighted materials it’s illegal only in countries where the right to make private copies doesn’t exist and/or those who are sharing are getting financial income for other people’s copyrighted work.

Anyway, check Jamendo, Internet Archive and Creative Commons

There are plenty of podcasts available in iTunes that give out free tracks everyday. Search for “Indiefeed” in the podcasts section and you’ll find free tracks for a lot of different genres. Also, The Current, a Minneapolis-based public radio station, has their “Current Song of the Day” which is another great way to find new artists. Just start subscribing to some of these podcasts and you’ll get free music automatically every day.

This site was linked from an anti-riaa site, and may be what you’re looking for:
http://legalmusicsearch.com/

Also: music.cnet.com.