Regardless of fair use, Weird Al gets permission: https://en.wikipedia.org/wiki/Weird_al#Reactions_from_origin...
>I ain't with that…I think that my song was too serious…I really…don't appreciate him desecrating the song like that… his record company asked for my permission, and I said no. But they did it anyway…
http://splitsider.com/2011/12/gangstas-parodist-revisiting-w...
He received permission from Coolio's record company.