The legal ruling that makes what he does legal even if he didn't get permission (although he does) is about parodies; it's not clear why you think that would apply here. If all he did was change the title and the phrasing of some things, it's doubtful it would be.
The closest equivalent I can think of here would be starting from a blank slate, producing the layout manually to be roughly the same (similar to recording the music from scratch to match up with the original), and then come up with completely original wording that's about something unrelated to the original wording. That doesn't seem anywhere close to what anyone here is claiming.
That's debatable and would have to be proven in court. Weird Al's works aren't really critiques of the original songs so a parody defense would be very difficult to make. One could argue that the humor in his lyrics could have been set to another tune to the same effect, making his appropriation of copyrighted material unnecessary and therefore not fair use.
The closest equivalent I can think of here would be starting from a blank slate, producing the layout manually to be roughly the same (similar to recording the music from scratch to match up with the original), and then come up with completely original wording that's about something unrelated to the original wording. That doesn't seem anywhere close to what anyone here is claiming.