Here's yet another clip of Allan Sherman performing on The Ed Sullivan Show, this time the telecast for April 24, 1966.
The song is "Second Hand Nose," a parody of "Second Hand Rose," a popular tune from 1921 which Barbra Streisand was performing in '66 wherever she performed. The original recording of it was by Fanny Brice, the personality Ms. Streisand portrayed in Funny Girl, the Broadway show from '64. It was probably just too tempting for Sherman, doing a "nose" song associated with Barbra.
A couple of interesting points about it here: Sherman himself had had a nose job when he was much younger and at time of this show, he was doing everything he could to alter his current appearance — losing weight, swapping glasses for contacts, letting his hair grow out, etc.
Also, he changed some lyrics. In "Second Hand Nose" as it appeared on his then-current album, in the part about him going to the plastic surgeon, he sang, "I've been to this office once or twice and / All his patients look like Barbra Streisand." Here, he sings — and he stumbles a bit on the words as if they're new to him — "He said if I can handle the finances / My nose will be the same as Cary Grant's is."
Near the end on the record, when he's singing about sitting with girls in his car, the line goes, "We'll sit there sniffing glue." Here, it's "They'll meet their Waterloo."
One suspects Mr. Sullivan demanded the changes…