The first television appearance of the quote is indeed in "The Five Doctors." This can be determined by searching the scripts online. The phrase does not show up before the twentieth-anniversary show.
Logically, there are just not many places prior to "The Five Doctors" where the quote could have shown up. Prior to the Doctor's Regeneration in "The Tenth Planet," there was no notion of regeneration, and the only appearance of the First Doctor between his regeneration and "The Five Doctors" was the "The Three Doctors" in season ten. However, by the time "The Three Doctors" was filmed, William Hartnell was in ill health (it was his last acting job, prior to his death in 1975), and he had only two brief appearances, filmed separately from rest of the cast. His lines in "The Three Doctors" do not include anything like the quote in question.
"The Five Doctors" was also shown before the existence of the massive Doctor Who extended universe, so it would be very unlikely for the quote to have originated there.