Okay, interest is there. Now I just have to find a way get some reaction to it.
I had made several attempts to define the title of Barbarian King, but wasn't happy with any of them. In practice they are the most powerful of the hundreds of clan chieftains, who are the leaders of more or less stable alliances of clans.
I made some demographic tables, and there are about 500 chieftains of individuals clans ranging from 10,000 to 100,000 people. While they are all independent there are lots of alliances of clans that band together and the leader can call himself a King. I tried basing it on the number of chieftains loyal to them, or the number of people under their command, but without a central authority that would establish and control such a standard it doesn't make much sense. So I guess it mostly comes down to whether or not you can pull it off calling yourself king without being rediculed by other chieftains.