Caledonii would be the tribes inhabiting Caledonia, the land. Think Americans and America. The word seems related to Celt, for what it's worth.
Grammatically, the singular would be Caledonius, but oddly, I cannot find Classical usage for this. It seems merely a descriptive adjective for geography/features of the land of Caledonia (such as "Caledonian Ocean," "Caledonian forest," and "Caledonian bear").
It's possible to use Caledonius (for a male, Caledonia for a female) in this way, but I'm not so sure it was ever done.
I also see online the people called Caledones. Again, though, no singular. A similar search in the Thesaurus Linguae Graecae showed up no singular. By parallel with Macedones (as Rafael points out in the comments), though, one could perhaps use Caledo (-onis).
That's not to say you can't use Caledonius, though perhaps in Latin you'd want to use vir Caledonius.
For English, Caledonian would be acceptable, though apparently not for a modern Scot.