Federalism. Particularly Dual Federalism.
The National Government will be limited to national needs, currency, foreign relations and the military.
The States (or Districts) will have their own governing bodies that the people living in that location can abide by.
The reason as to why this system would work is because Somalis tend to live in regions where their people (Qabil) live. Thus, Somalis would most likely abide by the rules and live in a civilized manner in State regulated government bodies.
As the perks of National Governing policies become apparent to Somalis living in every state, they will appreciate the National government itself.
However, I have a radical idea that might make a Federal State viable.
Having a "Clan-less" identity, as a prerequisite to joining the National Government. Or having the title removed while you're in office, regardless of the position. That way, those in the National government won't be looked at as a threat. Or forcing a representative from each Qabil, to form the National government.