This one is legal and free.
Spiralfrog
Quote from The Clark Howard Show Oct 09, 2007 -- Deterring your child from stealing music online:
"Fortunately you don't have to outright ban your children from getting free music online. There are several free and legal alternatives. SpiralFrog.com allows you to watch ads and get free downloads from major label artists."
Ad supported but free nonetheless.
EDIT: US and Canada only.