I noticed in the Veleia that my Priest can only change to the Paladin, Monk, and Warlock? Is there a way for my Priest to become a Barbarian?

If u changed it to a paladin, then that character can enter armoury guild. Then your priest can changed to barbarian in the armoury. However, barbarian do not learn any spell so not really advisiable for you to changed to barbarian. Warlock is better choice because can learn moon magic. But it is up to u.

I was considering playing again with just 2 priests and 2 wizards in my party. Here's what I was thinking, and yes, you can convert direct to Barbarian.

With one very early level priest, you take the Paldin quest, and join the Warriors guild. Then cancel the Paladin quest, and take the Barbarian quest at the Warriors guild. Once you the traps and locks skill and pickpocket skills are acquired, then switch to a Warlock. Level up to about 14-15 in Warlock, and take advantage of amulets of holding about Ishad to increase Strength to 24. From there the progression would be Ranger (to flesh out a few more vine spells), then Paladin (to get Crusade trait before Skull Castle). Then time for Samuraii and sun spells. The other priest needs to major in vine and spirit first as he is the party healer. Anyway, those are my thoughts, the variations are plentiful.