I've got a copy of "The Songs Of Scotland Prior To Burns" which was published by W&R Chambers in 1862. It claims that the song in a different version was first published in Johnson's Museum (ie that is the Burns lyric so dated between 1787 and 1796) and that the original is probably not that much older.

The original it gives consists of the chorus and both the first and last verse as used by Burns and sung in this youtube clip plus one other verse.........

"As he came walking up the street
The pipes played loud and clear
The young and auld cam out to greet
The Young Chevalier"