LOL. I’ve never seen. Puff Daddy’s appearance is literally the least random thing in that video!
Run DMC had Calvert Deforest (Larry “Bud” Melman) in their King of Rock video. It was a little random.
The two Mets are Keith Hernandez and Mookie Wilson.
The Giants are Sean Landeta (#5), Mark Ingram (#82), and Carl Banks (#58). Can’t read the jersey number of the guy in the back, and I don’t recognize him.
Ohh, man, John Candy as Yosh Shmenge. 
Found a list - it’s Karl Nelson.
That’s hardly “seemingly random” consider it’s a movie tie-in video for Terminator 2.
That could be a whole other thread, but the best of the movie tie-in video genre, which has the actor from the movie appearing randomly in the middle of it, has to be Princes of the Universe
Also in (two) Maria Carey videos, It’s Like That and *We Belong Together
- (along with Wentworth Miller, but he was just starting in Prison Break at the time so I don’t know if his previous roles would rank him as famous yet.)
Alan Rickman was in Texas’ video for In Demand.
Nichole Kidman appeared in Pat Wilson’s Bop Girl video.
Wasn’t famous then, but soon became much better known. So if you saw it a few years later, it would be a “What the ??” moment.