First, let me switch it up to remove the word God, since that word has so much baggage, and replace it with Being O, defined so as to assume that Being O (BO) is omnipotent.
What it boils down to is the apparent contradiction:
(A) BO is omnipotent
(B) BO is not omnipotent.
The question, if it has a strictly yes or no answer, leads to (A) and (B) being simultaneously true.
Yet the usual precepts of logic tells us that a statement and its negation can't be simultaneously true.
I believe the heart of the resolution to this apparent paradox lies in scrutinizing the assumption that the question must have a yes or no answer.
It's easy to argue that there are questions that don't have a strictly yes or no answer. There are a plethora of examples. "is __ tall?" "is __ warm?" "is __ large?" "is __ close?"
or even "is __ sentient?" and "is __ self-aware?" and "is __ intelligent?"
Pretty simple questions, none of which have a strictly yes or no answer. This little argument shows that the language we use to describe reality is a lot closer to shades of gray rather than black and white.
The first of two resolutions to the apparent paradox is that the original assumption, that the question must have a yes or no answer, is incorrect. One does not need exotic logics to deduce this. We have a tautology of the form (S1 --> (S2 and not S2)) --> not S1. S1 is the statement "the question has a strictly yes or no answer," S2 is the statement "BO is omnipotent," and the arrow stands for if/then, ie, conditional implication. Let statement 3 (S3) be the compound statement ((S1 --> (S2 and not S2)) --> not S1). By saying S3 is a tautology means that the S3 is true regardless of whether or not S1 is true or false and whether or not S2 is true or false. This can be proven through a truth table.
Note that we also can argue that (S1 --> (S2 and not S2)) is true by observing the structure of this compound statement which in English is "if the question has a strictly yes or no answer then BO is omnipotent and BO is not omnipotent."
Using modus ponens, another precept of formal logic, since (S1 --> (S2 and not S2)) is true and since S3 is a tautology, it follows that S1 is not the case. In English, it is not the case that the question has a strictly yes or no answer.
The second resolution to this apparent paradox is based on my earlier statement that the language we use to describe reality is a lot closer to shades of gray than black and white. If we relax the assumption that (A) and (B) must be strictly true or false, we can see that (A) and (B) can both have a truth value between true and false. There are many ways to view the third truth value: "maybe," "partially true and partially false," "neither true nor false," "unknown," "1/2 (if true is 1 and false is 0),"b where a, b, and c are elements of a poset with a<b<c," and perhaps others. (A) and (B) simultaneously having this third truth value is not a contradiction. This is admittedly an unsatisfying resolution to the apparent paradox since, for starters, this rationale can be applied to any paradox.
"Be as wise as a serpent and as innocent as a dove."