Weird Al gets permission and licenses for every song parody he makes. The legal definition of parody in fair use wouldn't exactly cover everything he does.
That being said, there's still occasionally times where he gets screwed over by the licensing machine anyway - either because the label forgot to ask the artist (Amish Paradise) or because the artist forgot to ask the label (You're Pitiful).