Yeah, since the Old Gods expansion there has been the Tribal government type, which can upgrade to a feudal kingdom or a merchant republic through a special decision.
Tribal governments are pretty interesting. They don't get any levies, even from vassals and have to call their vassals into wars as allies. The only holding type they can build is a temple or a special "tribal" holding representing tribal lands. The tribal holding produces more troops and gold the more empty holding slots there are in the province, and when the government upgrades the tribal holding turns into either a castle or a city.