In Britain (including Scotland), Brythonic Celtic predates Gaelic by almost 1000 years or so. Being spoken from Kent up to Glasgow and across to Wales. Some people even suggest that Brythonic was spoken in Ireland before Gaelic, but this notion begs the question... Where did Gaelic come from and when? But that's another story. Pictish (possibly Celtic) would probably predate even brythonic.

As to Gaelic and English in Scotland, The Highlands of Scotland were occupied by Picts and the Lowlands were occupied by Brythonic Celts. The Romans occupying the Lowlands during this time and when the Romans left in 407, they left a weak kingdom, but still brythonic. The Scots (Gaelic speaking) extended their region of Dalriada into Argyllshire, between 500 and 550. The Angles extended the Kingdom of Northumbria into Lothian, Berwick, Selkirk, Peebles and Roxburgh. As far as I am aware these areas are in present day Scotland. The Angles spoke a dialect of what is know today as "Old English". The Angles moved into this area about 540 -600, these are rough dates. As time went on, Scotland was left with 4 distinct areas. Dalriada, Pictland, Strathclyde and Lothian (Northumbria). In 625 the Northumbrian Kingdom stretched from the Humber to the Forth and was ruled by Edwin. In 685 the Northumbrians decided to try and extend Northumbria into Pictland and hence invaded the Picts, but this was a big mistake. The Northumbrian army was defeated by the Picts and eventually Northumbria lost supremacy to the Southern Saxons. (Also why RP is based on Southern English and Not Northumbrian ???). The Picts became the supreme overlords of the Scots in Dalriada and the Brythonic Celts in Strathclyde.

About 785, Pictland started to receive attacks from bands of Norse invaders and these lead to Pictish defeats and in the 830 (approx), the Norse invaders made permanent settlements.

In 843 Dalriada threw off Pictish control, where upon the Scots King Kenneth MacAlpine laid claim to the Pictish throne through the Celtic law of Tanistry. Followed by the union of the Picts and the Scots. The now "United Kingdom" tried to oust the Northumbrians from Lothian but were unsuccessful. At this time the Norse people occupied the Western Isles, Northern Isles and Caithness.

The Scots allied themselves to the English to get rid of the Norse Invaders and sometimes allied themselves with the Norse to get rid of the English.

It was not until 1018 that the Scots Kingdom managed to remove Lothian from the hands of the Northumbrians and in 1034 the Scots, Angles, British and Picts were a United Kingdom of Scotland.

As far as I am aware MacBeth was the last of the Gaelic Kings, and he himself was followed by Malcolm, whose wife (an English lass) moved the royal court to Edinburgh around about 1070. At this time many persecuted English people moved into Lothian from England due to Norman Conquest. The English who were persecuted in England flourished in Scotland.

The real point of all the above is that English has been spoken since the 6th Century in Scotland. Not all of it but quite a large piece. Modern Scots dates back to the first Angle invasions at this time.

Incidentally whilst parts of Scotland were English speaking, parts of England were still Celtic speaking eg West Yorkshire Kingdom of Elmet and part of Cumbria.

To sum up English has been spoken for longer in Edinburgh than in Leeds.

Nick Higham has written an excellent book on the history of Northumbria. (The Kingdom of Northumbria AD 350-1100)