Naja, ob das jetzt die grosse schöpferische Reimkunst war sei dahingestellt :) Mich erinnert verzagen auch zuerst an Gedichte. Aber diese spezielle Reim ist dann wohl eher in einer Kneipe entstanden, auf das Jahrhundert will ich mich nicht festlegen
Änliche Sprüche hat wohl schon sinngemäss Seneca geklopft:
Man muss nicht gleich verzagen, immer wieder wagen.
nicht verzagen taucht in recht vielen Gedichten scheinbar auf, hier siehst du auch schnell zugehörige Jahreszahlen. Oder hier
Ansonsten vielleicht mal Spruchseiten im Netz durchsuchen (Aphorismen,Zitate), auf die Schnelle hab ich da nix gefunden.
German slang websites similar to urbandictionary.com bietet auch noch viele Suchmaschinen