Many God believers say, God is timeless, or atemporal, he exists outside spacetime. Where there is no time, there is no change. But in order to create the Universe, God would have to have an impulse, the will to create it. However this and the very act of creating is a change. Yet, God is atemporal. Isn't that a contradiction?
I cannot speak for every system of belief in God, but here is one way I've been taught to resolve the problem you observe.
God being perfect cannot experience change, and so cannot experience a change in his will that would have created the universe "at an impulse." It is better instead, to say, while God is eternal, he is also a single Devine Act (identical to the act of being from Aquinas). He is, as many have drawn the analogy, the Author of a great work, who is not absent from the story nor bound by the same passage of time as the book.
As an example, one of the main creeds of Christianity discusses the precise idea of "verbs happening" before creation began. The Nicene Creed mentions that the Second Person of the Trinity "was born of the Father before all ages... was begotten not made," and that the Holy Spirit proceeded either from the Father or the Father and Son (depending on which branch). Since these things happened before "all ages," they proceeded time, and so it's not accurate (in this point of view) to think of them simply having happened in some time before Creation.
It is also a common refrain among Christian philosophers that God had no need of creation, so again, it is inaccurate to speak of an "impulse" causing God to create the universe.
Yes it is a contradiction. The Advaita philosophy says that the question can only be asked in the realm of causation; it cannot be asked or answered outside the realm of causation. In the realm of the atemporal God (the Absolute or Nirguna Brahman) there is no why, there is no cause and effect. An illusion can only be seen within the illusion, outside an illusion there is no illusion perceived. Swami Vivekananda says (Complete Works, V2, section Jnana Yoga, lecture The Absolute and Manifestation; available here - http://cwsv.belurmath.org/volume_2/vol_2_frame.htm):
What you call motion and causation cannot exist where there is only One. We have to understand this, and impress it on our minds, that what we call causation begins after, if we may be permitted to say so, the degeneration of the Absolute into the phenomenal, and not before; that our will, our desire and all these things always come after that.
But first we have to understand this that the very asking of the question "why" presupposes that everything round us has been preceded by certain things and will be succeeded by certain other things. The other belief involved in this question is that nothing in the universe is independent, that everything is acted upon by something outside itself. Interdependence is the law of the whole universe. In asking what caused the Absolute, what an error we are making! To ask this question we have to suppose that the Absolute also is bound by something, that It is dependent on something; and in making this supposition, we drag the Absolute down to the level of the universe. For in the Absolute there is neither time, space, nor causation; It is all one. That which exists by itself alone cannot have any cause. That which is free cannot have any cause; else it would not be free, but bound. That which has relativity cannot be free. Thus we see the very question, why the Infinite became the finite, is an impossible one, for it is self-contradictory. Coming from subtleties to the logic of our common plane, to common sense, we can see this from another side, when we seek to know how the Absolute has become the relative. Supposing we knew the answer, would the Absolute remain the Absolute? It would have become relative. What is meant by knowledge in our common-sense idea? It is only something that has become limited by our mind, that we know, and when it is beyond our mind, it is not knowledge. Now if the Absolute becomes limited by the mind, It is no more Absolute; It has become finite. Everything limited by the mind becomes finite. Therefore to know the Absolute is again a contradiction in terms. That is why this question has never been answered, because if it were answered, there would no more be an Absolute. A God known is no more God; He has become finite like one of us. He cannot be known He is always he Unknowable One.
We exist within the realm of causality, all of our perceptions and reasoning are dependent upon this. The question can only be asked within this realm.
Once we step out of the spacetime context we can no longer apply any reason from within the spacetime context ( impulse, temporal ) to the problem so we can't conclude any contradictions.
This doesn't mean there isn't a contradiction. There might be. Also such a question simply might be non nonsensical because it assumes the existence of something that may not exist (I'm talking more about things that exist outside spacetime than I'm talking about a god, though not saying god exists either).
Many God believers say, God is timeless, or atemporal, he exists outside spacetime
Otherwise he would be part of creation; or he would be creating himself.
Where there is no time, there is no change.
This might be debatable; Aristotle for example said that change was an aspect of time; and then suggested that change was motion.
Following on from this, Mach suggested that time was exactly motion; and specifically the motion of all the background stars - the stars in the far distance; essentially everything else except us.
Einstein tried to incorporate this into his theory of time (ie Relativity) but failed; however Julian Barbour recently found a way of making this quantitively explicit.
But in order to create the Universe, God would have to have an impulse, the will to create it. However this and the very act of creating is a change. Yet, God is atemporal. Isn't that a contradiction?
Not really; its the act of creation which is atemporal. Change is motion and temporal; ie within creation.
No, there is no contradiction! However, since you make several statements, I will address/answered each one separately.
1) God is timeless - this is true because, although God is multi-dimensional, time is not one of His dimensions.
2) He exists outside spacetime - this is "sort of" true, but it would be more accurate to say that spacetime exist "inside" God.
3) Where there is no time, there is no change - this is not true! Movement/change in four-dimensional space, does not require time!
4) In order to create the Universe, God would have to have an impulse, the will to create it. This, and the very act of creating, is change - whether God has an "impulse" or not, and whether He acts or not, makes no difference because whatever He does, takes Him no time to do it (per responses 1 & 3)!
In conclusion, there is no contradiction because "time" is not applicable to God.
Maybe gods will is more of a logical thing than a choice of some being. Much like the algorithm of a fractal. A fractal can only grow (or come into existence) when energy is applied to the right formula. Time is not required for the fractal algorithm to exist, in potency it exists without time. So in potency the whole fractal up to endless iterations already exists, without time. But in order to create the 1024th iteration, to bring it in to existence, you have to have time, because energy needs to be put in to do the calculations.
We people tend to anthropomorphize god. But maybe god is just "the right thing" that allows creation. Just like a fractal algorithm allows you to create endlessly. You can't be calculating a fractal and suddenly change the algorithm and expect to be still creating an endless pattern. You might be well ending up in a pattern with a dead end if you do.
In my view, gods will equals fractal logic. It is the only way to keep creating.
In that sence, yes gods will is timeless, and its will to create isn't a contradiction with being timeless.
EDIT: In addition to creationism vs evolution: I believe we are part of both. Initially we were created and 'let loose' to evolve. Much like a programmer can create artificial self learning intelligence. It is created, yet it evolves. And where is the beginning in that? There is none, I believe its a fractal pattern with no beginning nor end :)
I like to answer such question not with the bibel but just with reasoning.
1st: I think we can't understand god itself. So we don't know if our description of dimensions and our picture of everything is right. I like to think more about god as a thing existing in everything. This is my definition of not picturing him. So saying he created something is maybe not quite complete. I think he is part of our world too and he is here. So it is not like building a lego tower, it's more like forming and changing things in a ordinary manner. So with respect to our world maybe more like making a stop motion movie about a part of your own. I think the laws of nature can be as well described as god. They are not predictable and our understanding is and will be forever incomplete.
2nd: Another though which is similar to the first one; for god our world is like for us a painted image. He sees everything, the space and the time at once. Maybe his interest are more about varying things like a painter would redraw a part of his painting. So it's not unreasonable if he sees everything at once that he would create things. He just creates thing in a way we don't understand which changes in our whole timeline simultanious, so we would not even now that he changes something because for us it would be just a natural thing which we remember of our childhood. So god has not the same time as we have.
P.S: My favorite definition of god is as a thing which is everywhere and something we can't measure. It's actually really about not making a picture of god. For me the answer if god exists or not doesn't matter anymore. The more important thing above religion are more the ethics which have every religion in common, be kind to people, treat the other like you want to be treaten and all this messages. I think religious fights are the real contradiction.