As stated, parodies are protected. Also, as stated, venues which provide live music to their patrons pay ASCAP. Look at the front window or front door of the club. You'll see a yellow triangle ASCAP sticker on there.
There are a lot of different 'rights' involved here. Sync rights, mechanical rights, performance rights, master use.
sync rights - you can use the previously recorded song in 'sync' with your commercial, film, DVD whatever
mechanicals - this lets you record a song AND distribute it.
performance rights - these are the things that radio stations, clubs, coffee houses etc pay the publishing companies (ASCAP, BMI etc) so they can play music publicly.
reproduction right - you can make copies of an existing recording and release it yourself. Like a compilation CD
The "recording of a certain work" and "the performance of a certain work" and "the certain work" itself are three completely different things. You cannot just go around re-recording other people's works without paying them. Whether those are songs or if they're literary works. However, if you get the right to re-record somebody's copyrighted work (song, book) then the rights to the actual recording of your voice belong to you.
IANAL, and I haven't dealt with music rights in a number of years, but I believe the above to be accurate. The Harry Fox Agency used to deal with things like this but, afaik, they've gotten out of part or all of it.
EDITED TO ADD:Here's some info from BMI's webpage:
http://www.bmi.com/licensing/license.aspHere's some from ASCAP's:
http://www.ascap.com/licensing/And it looks like Harry Fox still does this (as I think about it, I believe they just dropped out of the "sync license" business). Here's their FAQ page:
http://harryfox.com/public/FAQ.jsp