"Everything that was old is new again"

I just quoted this in the Pit, but where does it come from? Google got me “about 43,100” hits, but no one seems to attribute it, and several quotation sites I tried were no help.

It’s from a song. Scruff furkles around:

IMDb has the song credited to All That Jazz with a date of 1974 and attributed to Peter Allen. And all that link

I don’t know if that’s the original.

Well, maybe, but I rather had the feeling that it had a more venerable origin than that.

I also thought that the “that was” was integral to it. However, I tried searching Google Books and got a lot more hits for “Everything old is new again” than for “Everything that was old is new again,” so maybe I am wrong on that score. I still did not find any more clues about its origin though.