I'm not quite sure, but I think any barbarian faction can build shrines if they want.

I suspect you have to have a christian leader to change the state religion to christian, but I havent tried changing yet.