priests

[Gandalf Parker]

(Im beginning to feel like a fanatic bringing the same thing up for every problem)
There is also an option of assassins/seducers casting Charm or Hellbind. Steal some better priests from a nation that has them. You can even steal their prophet and get multiples. Do damage to them at the same time that you are benefiting yourself.

OR if you want something less aggressive but abit more difficult to arrange, you can trade for them. Trading for mages and priests is possible. The person simply moves that unit to a province owned by you where you have mages lined up waiting to cast Charm or Hellbind. (that used to be much easier before Wind Ride got nerfed)