In the strict first amendment sense - no he isn't (with the possible exception of the Nirvana one)
The parody protection is very narrowly defined, mainly to stop the target using it to squash opposition. You can't automatically use artist X's tune/style/etc to parody politician Y. And just making your own funny version of something is definitely not
The first amendment has nothing to do with this, as far as I know. The question of parody is entirely in the realm of copyright/trademark law.
Can you give more information about how parody is defined in the context of fair use here? My understanding is that Weird Al would be completely within his rights to make all of his parodies without permission from the original artists, and that he only seeks there permission out of courtesy and a desire to maintain a good relationship with people. The Wikipedia page backs me up on this, although we could both be wrong.
In Campbell v. Acuff-Rose Music Inc. the 'live2 crew' won on their parody of "Pretty Women", because they were making a comment on the original song. While family guy lost "when you wish upon a weinstein" because they merely appropriated the "when you wish upon a star" song to comment America's stereotype of Jews. But they weren't saying anything about the song.
Basically I can parody your work to make a comment on it. I can't appropriate it to parody someone else.
Weird Al gets permission from the artist - but that's mainly a, don't cause trouble, keep the record company happy.
He would still have to pay for the rights to the music owners when the song is used, although the owner of the music rights may well not be the artist. Which is why some songs are performed live but not on the albums - the payment for singing "happy birthday" at a concert is very different from putting out a cd of it.
ps - I am not a lawyer - although my dog has been trained to piss on their BMWs
The parody protection is very narrowly defined, mainly to stop the target using it to squash opposition. You can't automatically use artist X's tune/style/etc to parody politician Y. And just making your own funny version of something is definitely not