Hrafnkels saga is a solid example of this, as Samr chooses to banish Hranfnkel rather than executing him ...
Well you certainly know how to win me over real quick, don'tcha?
1. Norse societal structure isn't dramatically different from the rest of Feudal Europe. In fact, even as "pagans" there were instances of Vikings serving in courts or owning lands under a Christian lord. Much of their own structure is roughly comparable to Christian nobility positions, and is mostly already in game (Jarl similar to Duke, Chief similar to Count, ect). So... that's a plus, at least as far as Norse is concerned.
Indeed. I never did understand why people think all the places would have such massive issues with the base mechanics. The only thing really needed is to set Crown Authority really low so vassals can pretty much do what they want when it isn't directly conflicting with their Lord's basic rights. The biggest Mechanic-problem is the Religious screen, since it'd need reworking for more proper Hofgoðar/polytheism functions, not a "Pope of Óðinn".
This is why terms like "Pagan" are so very terrible. They aren't one thing, yet people pretend that they are (and are still somehow able to explain in minute detail the distinctions between Waldensian and Cathar heretical philosophies..). Tengriism is not Ásatrú, Ahura Mazda is not Ukko (Finnish Sky-God) and there is no such thing as "Paganism". It's just a Christian-centric superiority complex (and somehow Zoroastrianism was uniquely excluded from this group even though Christian texts from East-Rome explicitly calls them "pagan fire-worshippers").
3. In Christian society, mercy is viewed as a good thing. In Norse society, it can be seen by some as a sign of weakness. Right now when you release someone from prison, all your vassals approve due to your merciful actions. Norse folks shouldnt' work like that: with maybe a few exceptions of the less-violently inclined traited folks, you should gain respect for executing a defeated enemy, and lose respect if you allow them to survive. Hrafnkels saga is a solid example of this, as Samr chooses to banish Hranfnkel rather than executing him, and everyone views Samr as weak for doing so... and then don't help him out when Hrafnkel builds a new force to come and reclaim his home from Samr. Of course, afterwards Samr is given the option to either die like a man or survive, and he chooses life (despite it ruining any chance he had to be looked upon with honor again for the rest of his life). So all of that could make for fun game mechanics... choosing between killing someone to appease your fellow vassals/peers and risk the potential wrath of their relatives, or let them live in order to not piss off their family but be looked on by your vassals/peers.
Yes, the results of traits should have modifiers for their effects that'd state "christian = { }" or "norse_pagan = { }" to let there be exceptions to the rule (so stated religion or religious group uses the modifiers within the parameters instead). The Tooltip for the trait "Lustful" in CK1 goes into this, for example, since it mentions that even though it's considered sinful behaviour for a Christian it would be positive for heathens since the associated fertility would be viewed as a blessing (I mean find me a Vanir that doesn't have some mention of fertility as an attribute!).
It'd also help with good ol' situations like Normans keeping their "Danish wives" (legitimized mistresses). Just because they convert to Christianity doesn't mean they don't still keep attributes that used to be positive for them, all of a sudden they could be marks of great shame and targets for ridicule. Holdovers from the old ways when "they didn't know any better". Might find themselves in a really strange world if they play the Norseman straight for gameplay advantages but ends up pressed to convert if eventually losing against Christians, then being stuck with decisions made when they were the Min-maxing thing to do.
Just a few random thoughts, like I said. Figure the Norse would (compared to some of the other Pagans and the Muslims) be easier to nudge into the right direction than the other non-Christians, since they have such a strong history and shared ancestry with the rest of Europe, thus their society isn't as dramatically different from Christian Europe (as the other non-Christians.)
Of course, they're also one of the smallest non-Christian groups and seem to have a potentially short shelf-life (especially because Erik The Heathen seems intent to convert to Christianity at his first opportunity, and he's just about the only Norse leader with any major pull). But hey, I can dream can't I? Maybe I'll figure out the character ID numbers for Erik The Heathen and Olaf Green and some others, just so I can have fun still if or when they became playable regularly.
They're not huge any more - although they're dramatically underpowered in Sweden to give the Christians an edge in winning. It's rigged to usually have Uppsala lose even without the shady honourless tactics resorted to in the actual Civil War - but they're still one of the biggest potential game-changers for non-Christians. Lithuanians and their kin, while resilient and longer lasting, were still an enclave in hostile lands. Vast land-based Christian forces on all sides but the sea and when Uppsala fell to Christians even that sea became a front in the war. But if Ásatrúar end up winning Sweden then it'd also mean that the Baltic is foreign water for all Christian nations (surrounded by Lithuanians, Finns and Swedes - all "pagan"). The Northern Crusades become a much tougher ordeal to successfully accomplish and Swedish warriors would not be dying in the forests of Finland to create "Österland" and Christianize the Suomenusko heathens. Who knows what might happen.
Though the hyper-interventionist Emperor might be trouble for that in the Game-Universe. When was the last time a German Emperor had 20 000 soldiers trying to occupy Närke, again? Must've missed that in History-class.