I'm afraid you've been misinformed. There certainly were kings in Scotland prior to Cinaeth mac Alpin (Kenneth MacAlpin). The rulers of Dalriada in Argyllshire were kings, not merely chiefs -- the Gaelic title was "ri" (king). Similarly, the Picts or Cruithnigh in Scotland were also ruled by kings. The medieval annals and other sources are filled with references to "kings" of the Picts and "kings" of "Alban" or of "Dalriada." I own several compilations of the medieval annals and chronicles, many of them contemporary primary sources, and they unanimously refer to the rulers of the Picts and Dalriadan Scots as kings, not chiefs.
Highland clans, with chiefs, were a later medieval phenomenon. The institution of clan chief arose after the union of the Picts and the Scots under a single king, and thus the various petty kings or subkings of the Picts and Scots were reduced to the status of mormaer or count or earl.