Anyone has any experience with adding new holding types besides tribes/castles/cities/temples/nomads?
It is impossible
Depending on what you want you can have some turnarounds though.
For my L3T mod i created some holding specializations. For example a temple holding can be assigned to be either a monastery or an episcopal see. The holding name, title and picture remain unchanged though.
Technicaly, a specific building is assigned to them by event, that building locks what further building chains you can build or not. That way you've got some holding differenciation.
To make a visual difference, I apply an icon through an holding modifier.
You can put the restriction/specialization through such holding modifiers directly (it just didn't existed when i created my mod first). Province modifiers can be used to some extent (i am using them for economic ressources, unlocking some building chains in the holdings.