If you type in exact phrase search of the British Newspaper Archive search it helps. Then it gives a date range to narrow it down further. However, the Optical Recognition software that they used often gives misread gibberish characters - so it's hit and miss as to what comes up. Then you have to pay to actually see the full entry.

From this index there seems to be an entry 'Brave Scotland' in an advert from 1891 for the fourth edition Simon Fraser collection. However, I am seeing the two words without full context. So it may not be real.   I found FULL free download scanned PDF's of an 1870'S edition of Fraser's collection and an earlier edition - neither contain the title 'Brave Scotland' or 'Scotland the Brave' etc.