It's certainly possible. I'd note there are a variety of services who exist solely to provide "in store music" to stores, which handle all the copyright/broadcast rights etc....and they are generally pretty affordable.

Still I wouldn't be surprised if there was a discount for stations that are pure public-domain or if small franchises were just playing it themselves (though presumably the recording/performance itself is still protected and they might not be in the clear legally if they were say, just playing a CD)

>I'm starting to think that we need a free music movement,

It already exists, it's called the Open Source Movement (well, amongst others). There is a variety of music available under say, a Creative Commons license...and many websites devoted purely to free-music.