That's not necessarily true, — As lucid said earlier, companies will find ways to get you.
smitchell, it's a pretty blurry line you're treading. I can tell you for a fact that it does not matter if your game is free or not in the case of infringing on copyright. Plus, YouTube also has agreements set in place with all those record companies so that they get paid in ad revenue. As for "big games" with "big songs" in them, the game companies are licensed the music, which is likely a sync license (that's what movie studios and television networks pay for when putting an artist's song in time to a visual medium). I say likely because I'm not entirely sure on how it works with licensing to video game companies, but it's the closest thing I can think of. Either way, sync licensing terms are made up on a deal to deal basis.
You "advertising" or linking to places to purchase the music also isn't going to help your case. The copyright owners have a lot of rights to their works, among them include dilution or defamation, or some similar term. Basically, they can sue you for using their work in a product that would hurt their own sales or reputation by having their work associated with something they don't support, whether it be a cause or an indie film or whatever. Dumb things like that.
You obviously won't be able to obtain a sync license deal from any big name record companies or artists. What you CAN try to do is find indie artists who have released their works under Creative Commons Licensing, which would allow you to do exactly what you want to do. Big name bands are largely out just because their music is also owned in large part by the record labels they're under.
Indie doesn't mean bad though, and neither does Creative Commons. A good example would be Jonathan Coulton, who has released all his music under CC, allowing you to screw around with it and use it in derivative non-commercial works as long as you credit him for the music.
Each Creative Commons License allows something slightly different, but it's still a pretty sweet (read: infringement free) deal.
You can read more about it here: