First things first.

1. Make sure everyone accept the non-contradiction principle and mark the ones that don't as "beyond therapy" (or patiently explain that "truth" business to them).
2. Make sure everyone use the same definitions for the subject at hand.

My limited experience tells me that most theists will readily accept point one, believing that there is a God, and I'm mistaken to believe otherwise. I praise them for their coherence, then move on to what we actually mean by "God" and such.

EDIT: I may need to be more explicit: I think the non-contradiction principle is more fundamental than the possible existence of a God, and as such should be settled first. Settling the definition for any particular question always come second. It only seems to come first in most discussions because the non-contradiction principle is generally common knowledge.

Also, I do accept there is a good chance the theist and I do not put the same meanings under the same words. It's just simpler to assume we do when using them as an example for discussing non-contradiction: we don't need to use the actual meanings yet. (Well, with one exception: I assume "there is a God" and "there is no God" are mutually contradictory for any reasonable meaning we could possibly put behind those words.)