I am not a copyright expert, but I do own a few of Weird Al albums and he is very diligent about obtaining permissions from artists he is covering.
IIUC, Weird Al probably doesn't need permission for his parodies, legally speaking. He does get it anyway.
It’s not a copyright issue, it’s a right of publicity issue, a completely separate legal issue (conceptually, more trademark-like than copyright-like, but distinct from either.)
It's not just about seeing a celeb face. There's more going on that was discovered in the 80's and 90's, I think (that's when it became a big thing at least).
Built into it is the implication that the celeb likes the product. Additionally, products and branding have become a part of our personalities (IMO bad trend). So in a way you can BE like the celeb.
You will be just as cool as michael jackson if you just hold a pepsi in your hand. Sure, none of us really think this at face value, however it's implied and hinted at.