Your conditions don't require that the next church for a given pastor be randomly selected. Couldn't you just iterate through the church list?
That is, assign each pastor a number, 0-12. Assign each church a number, 0-12. The first month:
pastor-0 --> church-0
pastor-1 --> church-1
pastor-2 --> church-2
pastor-n --> church-n
The next month, just increment one of the counters (with wrap-around)
pastor-0 --> church-1
pastor-1 --> church-2
pastor-2 --> church-3
pastor-n --> church-0
Then repeat for the remaining months:
pastor-0 --> church-2
pastor-1 --> church-3
pastor-2 --> church-4
pastor-(n-1) --> church-0
pastor-n --> church-1
There's a very simple loop to all this (O(n)). If it's confusing to you, I suggest trying the loop on paper with say n=3.
If the randomness is a requirement then please update your question.
EDIT BY PAX
I'm deleting my answer and up-voting this one since it's O(n) and the expansion of mine to cater for the edits would have been at least O(n^2).
You can still have randomness by making the pastor-0 through pastor-N values indexes into an array of pastors that has been randomly sorted so that makes this solution at least as good as mine.
END EDIT BY PAX