If time doesn't exist (this Wikipedia page and this SEP article provide some arguments for the non-existence of time), does that mean God doesn't? Given that it is impossible for God to exist completely outside any sort of time (how would he create anything if he can't change?), how could he exist if time can't?
First of all, God does exist outside of time, so there's nothing impossible about that. That's what is often referred to as God existing in eternity. Concerning the creation, Augustine specifically addressed that question:
"Those who say these things do not yet understand thee, O Wisdom of God, O Light of souls. They do not yet understand how the things are made that are made by and in thee. They endeavor to comprehend eternal things, but their heart still flies about in the past and future motions of created things, and is still unstable. Who shall hold it and fix it so that it may come to rest for a little; and then, by degrees, glimpse the glory of that eternity which abides forever; and then, comparing eternity with the temporal process in which nothing abides, they may see that they are incommensurable? They would see that a long time does not become long, except from the many separate events that occur in its passage, which cannot be simultaneous. In the Eternal, on the other hand, nothing passes away, but the whole is simultaneously present." (Confessions, 11.11.13)
The key to understanding what he is saying is to remember that any concept whose meaning depends on a temporal idea needs to be omitted from any questions or descriptions of the eternal. For this reason, even the term creation must be understood in a way that does not imply time or change. From the human perspective, the creation involved a series of events in time, each of which involved change. However, from the divine perspective, the creation must be seen as an eternal expression of God's will. We see it as a change, but there is no reason to assume that He sees it that way.
It's interesting that many mistakenly think of God's existence in eternity as a limitation to what He can do or how He is, but that's really looking at it backwards. Existence in eternity implies a liberty that is not easy for us to comprehend since we are subject to temporal constraints. How could freedom from these constraints ever constitute a limitation?
One potential solution to the paradox is if we view God's time and the world's time as existing differently. Picture the universe as a book. From the point of view of the characters in the book, time begins on the first page, and proceeds through to the last. But from God's point of view, the entirety of the book exists in one single moment of time.
You might object, however, that this still implies God exists in some sort of time context --without time, how could an act of creation (or any act) take place?
Whether or not this is an insurmountable objection really reduces to whether or not you're willing to grant that God's "time" might be outside the human ability to visualize or understand. Whether or not God is bound by any comprehensible universal laws is an old debate that will probably never be resolved. Suffice it to say that many theologians would be quite happy to discard your premise that God cannot exist entirely outside of time.
It's a great question but I feel it's too difficult to write an answer without a day to do it. The usual explanation would be that God does not exist in the way we usually define existence, and as Keith Ward explains in God: A Guide for the Perplexed this is the classical Christian view. The nub of the problem is the word 'exists'. The sages often claim that nothing really exists, including God. But this is a careful use of the word, since it distinguishes between what (seems to) exist and what is real.
Your reasoning seems fine, without time God cannot exist, but yet he can be real. Not everyone would use the word 'God' for what is real, which is why the perennial philosophy may sometimes appear to be atheism and at others theism, and in truth these words are simply inadequate. You might like to google Nicolas de Cusa Vision of God. You'll see that language runs into problems once we journey 'beyond the coincidence of contradictories' or, that is, beyond the categories of thought.
A huge topic that really needs a book for an answer.
The word "time" is misleading: what REALLY exists are objects that can evolve, mutate or cannot, that's ALL. In our universe everything is made by infinitesimal particles which are free to move and mutate. If an object can mutate we can say - just for convenience - that time exists for that object, if it cannot, time doesn't exist for that object: it's frozen. A mutation can then be measured by comparing it to a standard reference mutation, but time can exist even when it cannot be measured! Without measuring it, here time for an object consists in a sequence of states to go through, where we can see that time goes by in that an old state of the object - which exists BEFORE - is lost forever and replaced by a newer one. In your question you say that since time doesn't exist, God is not free to mutate. The opposite happens: since God of course makes what He likes and is free to mutate, then we can say that time exists for Him. God indeed had to mutate since we are sure that He had to make decisions concerning us and the universe to come, with surely existing "BEFORES and AFTERS" those decisions. All that was in a sort of non-measurable time, since besides God nothing else existed as a measuring reference. Since it's impossible to measure that time and give to the single steps of the creation any length, the creation should be represented as a single point and only be characterised by the order in which that "before-after" sequence took place in it. Any time prior to the creation (an alleged "time infinity") cannot be measured and is thus included in that single point too. To recap, an object has not restrictions whatsover given by any external clock in its mutations, if its particles are free to move it just mutates independently as a clockwork. Also God simply did what He intended to do without any external "time" restrictions, in an unknown sequence. That sequence represents the God's (unmeasurable) time.