The answer here is that Satan (as well as other angels) either did not know that God was indeed all-powerful, or what the meaning of all-powerful implies. As a Christian, I have come into many debates about the idea of Omnipotence, and everyone is familiar with the conundrum, 'If God is all powerful and all knowing, how can he be all good?' Satan is obviously familiar with this (in fact, I would not be surprised if he is its inventor.) The implication of this conundrum is that to make sense of God, you need to drop one of those three attributes.
Some Fathers are of the opinion that neither Satan nor the other angels were, prior to this, fixed in virtue and goodness, and thus were in a state where they could either decide to obey God or not. We must not overestimate the knowledge of angels, nor assume that because we now know something (such as the nature of the Trinity) it was always common knowledge of angels. It is clear in the temptation that Satan doesn't realize that the man Christ is God; so Satan repeatedly misunderstands - possibly willfully - who or what God is. To be fair on this one, pretty much no one knew exactly what was going on, even the demons who knew a bit more than the average person, but as Satan evidences, not a whole lot.
Finally, it seems to be agreed upon in all oral tradition that Satan's pride is the cause of all of this; his misunderstanding of God, (or shall we say, his assuming certain things about God) and his decision to rebel. It seems obvious that if you knew what God is you would never rebel (what would the point be?) but all of us know of people who apostatize - essentially deny what they knew before. Therefore to some extent it is immaterial what knowledge Satan had prior to his rebellion; he rejected it. We see an image of this in the man Judas Iscariot, who despite working miracles and being with the Godman, turns on him anyway. The cause in Judas' case seems to be considered Envy, so we also can't discount envy in Satan's rebellion as well, given its similarity.
There is a story told in our tradition that goes as follows.
A certain saint had love for all creatures, even to the point that he
prayed for Satan and the demons that they might repent. At the instant
that he prayed this, Satan appeared to him and snarled, 'No, it is God
who needs to repent!'
In the end, there is always the 'mystery of iniquity' as Paul says - the choice of the naked and inexorable will, even over and against all sense, all truth, all beauty and all goodness.