You have two options: to stop being tribal you will need to reform your pagan religion and adopt feudalism or you can stop being pagan. If you border an organised religion there is a chance they will send missionaries, if they do allow them to preach and eventually you will get an event to convert. Alternatively try to get some courtiers who follow an organised religion (invite them, kidnap them when raiding etc) and have them educate your heir who will likely flip to their religion.
Having said all that, I would say that elective gavelkind is superior to normal as you get to choose who will be the primary heir, i.e. who your next character will be, under normal gavelkind it is always your eldest son.