After you have built your Church and it's reached level 3 add the option to "recruit" a single Priest to send with the Army. He would only be able to travel with a Paladin and he would reduce the speed of the army to Noble speed. His presence would increase the faith of the Army by a set percentage when they travel outside their province to attack. A Priest cannot be sent as support.
Now, I have read all the back and forth on this suggestion and near the end it got off topic. Raith I have to agree it is similiar to your idea of getting more than one pally after a certain number of villages, but like booniesman88 said, like most people that come into the forum he did not read all the suggestions just to copy yours.
Gentlemen all suggestions are valid.
We know that in real military life the chaplain can not carry weapons. So a spiritual advisor would play well with defensive troops, but not work like a pally with Offensive troops. This could open up more weapons of the Pally of a non-defense nature if you take the defensive weapons away.
It would give you an advantage on both fronts to have something like a priest in the suggestion.
This may be a way to get us that extra "Pally", but in the form of a defensive Priest.
As for play style of Turtles. Please discuss that topic not in this thread.