The Reverend A.B. Scott, in his 1918 book The Pictish Nation, its People and its Church gives an interesting dissertation on the origins of ancient names for Britain and Scotland.
According to him and various other authors, the early Basque seafarers from the north of Spain, as well as Greek shipmasters navigated around the British isles and referred to them as Alba or Albion (meaning "white"). Ptolemy spells it as Alouion around 127 AD, and later on Pliny refers to the island as Albion. It was the Greek seafarer Pytheas, who as early as 300 BC refers to the islands Pretanikai Nesoi (meaning "Pretanic Islands"), which Scott claims is based on the native name for Britain Ynis Prydain, which literally means Picts' Island. Another scholar, Kenneth Jackson derives the name "Pritanic" from the Pictish tribe called Pritani, meaning "The People of the Designs."
Across the water, early Irish writers echo the "Albion" name and refer to Scotland as Alba or Alban, although the later Annals of Ulster refer to Scotland as Cruithintuait - the word Cruithni (meaning "the tribe of the designs") being the Irish word for the Picts and tuath for people, land or nation. The Vikings, upon landing in the north of Scotland at the beginning of the 9th century, called the country Pictland. The name Pentland Firth is derived from the Norse name Pettaland Fjord, literally "Pictland Fjord." In Britain, the P-Celtic speaking Britons spelled the Irish name "Cruithni" (Pict) as Pryten; this eventually becomes Briton in the tongue of the Teutonic invaders.
The Romans referred to Scotland as Caledonia, a name obviously derived from the Pictish tribe Caledonii, which fought Agricola at Mons Graupius in 84 AD. Finally, when Kenneth MacAlpin usurped the dual throne as King of Picts and Scots in 845 AD, he called the crown Rex Pictorum or "King of Picts." However, by the beginning of the 10th century, his descendants changed to "Rex Alban," which is then translated as "King of Scotland" or "King of Scots."
Historical records also add some variations. In Historia Britonum, Irish additions refer to the northern British mainland as 'O chrich Chat co Foirciu which means "From Caithness to the Forth." Myth also has it that the first Pictish king Cruithne had seven sons who gave their names to the seven Pictish subkingdoms of Fidach, Fib, Foltaig, Fortrenn, Cait, Ce and Circinn.
The Gaels, or Gaidheal is the name by which the Q-Celtic people who settled in Ireland after migrating from Spain and western France were known. The Gaels of the north were of the race of Niall, the western Gaels were of the race of Brian. The Gaels who settled in Argyll were of the race of Erc and related to the Nialls; Incidentally, the name "Scot" appears in the writings of Claudius who describes them as allies of the Picts. Even as late as 800 AD, the Norsemen refer to the Dalriada Gaels as "Scots" and the Picts as Picts.
