On Jan. 1, 1883, "The Evening News" of Portsmouth reported (p. 3) that

"Just as the clock rolled the knell of the parting year the band of the Black Watch, which is stationed at the Cambridge Barracks, struck up 'Auld Lang Syne,' followed by 'Good New Year' and 'Scotland the Brave.'"

That would seem to be the earliest reference to a tune by that name - the modern one, one hopes.

The "Belfast News-Letter" (Jan. 28, 1888), p. 7, mentions that
"Mr. Thomas Harper and Mr. George Vance" performed "Scotland, the Brave" as a flute duet at a social gathering.

According to the "Dundee Courier and Argus" (Sept. 12, 1894), p. 4, the band of the Gordon Highlanders marched to the Town and County Hall playing "The Hieland Laddie," "Alison's March," and "Scotland the Brave."

I don't know when the tune was first published (or perhaps recorded on wax) under the familiar title.

(The above information comes from the Gale-Cengage database, "British Library Nineteenth Century Newspapers," which seems to be available only through libraries. I could find no pre-1918 mentions in "The Times.")