Here's another idea. Iceland could start as a group of irish monks with a bishopric and around the time that the norse actually arrived the bishop would get a decision to leave the island and would immediately be replaced by a randomly generated norse character, the county would become norse/norse, and the bishoprics would become baronies.
Obviously there would also be a similar event for if the norse invade in game.
Obviously there would also be a similar event for if the norse invade in game.