6funswede, the person who posted the 60s Lehrer videos on youtube, writes on his myspace page:
"Sooner or later Mr. Tom Lehrer will appear in glorious and timeless black and white on American TV in a recording from Europe in 1967. I know because, in fact, it is one of the songs from The Tom Lehrer Wisdom Channel on YouTube that will be shown to the US audience in full broadcast quality…
Hint hint: People in Germany and in the United Kingdom will also have to watch out for some rare full broadcast quality Lehrer songs on TV. I’m not going to tell you more than that."
http://blog.myspace.com/index.cfm?fuseaction=blog.view&friendID=257452660&blogID=426498827
Also on youtube, from user flashbackcaruso, are 5 Lehrer appearances on “The Frost Report” and 3 renditions of Lehrer songs by Marty Feldman from his 1974 series.