Wierd Al pays royalties, but I don't know how much something needs to be changed to be considered different.

Technically, he doesn't need to pay royalties for the lyrics, because the lyrics are an original work. IIRC, parodies fall under the fair use exemption. However, he would still have to pay royalties for the music.