This is one of those cases where it helps to use some formal logic, because one of the things formal logic is especially good at is exhibiting the scope of operators.
Suppose we use the propositional symbol G to represent the proposition "There is a god". We can overlook the issue of how to make sense of attributing existence to a thing. And let's use ◇ as a modal operator that we will understand as "possibly". We can overlook exactly what kind of possibility for the present purposes.
When you say "God may exist" this is naturally understood de dicto as "It is possible that there is a God". So we might write this as:
◇G
When you say "God may not exist" the negation may sit inside or outside the possibility operator. So,
◇¬G
means "it is possible that there is no God", while
¬◇G
means, "it is not possible that there is a God".
The sentences ◇G and ¬◇G together form a contradiction, so they satisfy your criteria that they cannot both be true and cannot both be false. This is entirely consistent with bivalence, excluded middle and non-contradiction.
The sentences ◇G and ◇¬G are not a contradiction. It is possible there is a God; it is possible there is no God.
We might also add that ◇(G ∧ ¬G) would be a weird sentence stating that it is possible for the contradiction "there is a God and there is no God" to hold. This sentence would never be true in what are called normal modal logics.
I think that answers your question. Things get more complicated if we combine modal logic with quantifiers and write things like:
◇(∃x)Divine(x)
or even
(∃x)◇Divine(x)
This introduces all kinds of additional problems concerning how to understand potential existence and potential properties, and how to quantify into referentially opaque contexts.