Coincidentally I was just browsing YouTube and came across this clip of Johnny and Tony Joe White (who wrote the song) performing Polk Salad Annie. The user has a nice selection of videos from the Johnny Cash Show.
and this clip
.... The Tonight Show - 1980 - .... about working with Elvis....
I heart Johnny Carson. One of the classiest and funniest.
also a clip from the Dean Martin Show. At 0:44 Glen Campbell does an impersonation of Heartbreak Hotel. He sounds a little bit like the cartoon character Johnny Bravo, who is just as hilarious as Dom DeLuise.