I'm going to modify your question in three ways that I hope you find amenable. First, I'm going to make explicit the assumption for this argument that there is no God or that if there is a God, the fact of this God's existence is irrelevant to self-awareness. Second, I'm going to avoid the word self-aware because as I understand the term some animals, like dolphins or chimpanzees, might qualify for this insofar as they can recognize themselves in a mirror. So let's call it evolves socially (as you do at one point).
Third, I'm going to explicitly assume that an individual thinker can have the benefits of social evolution whether or not they themselves believe in God. To wit, there are atheists in our society who are socially evolved, and this means whatever the process of social evolution is / was, it does not need to be repeated individually.
With these three assumptions, the question boils down to whether a belief in a God could at some point have such great utility that it is impossible for a different route to achieve the same benefits (or at least so improbable that it won't happen). I'm sorry for the large degree of couching going on with these claims.
There are two possible benefits for social evolution that I can imagine arising from a belief in God:
a foundation for uniformity in the world. First, it helps to have a psychology where you think that cause leads to effect rather than everything being wholly random. Second, at some point, you will need to start doing numbers-based science in terms of social evolution.
A God can help with both of these moments by helping us to have that sort of expectation. (My sense -- and I'm not an anthropologist -- is that this type of benefit is maximized wit monotheism).
A foundation for morality. Here, this view can be seen as an enforcer for why we should not do bad things to other. In other words, this seems to work as a psychology social contract enforcement mechanism. Interestingly, it is also Kant's belief. For Kant, the only way to make it rational for us to act rationally in light of the immorality of others and our witness of the benefits that accrue to them is to believe there is a God who evens things out. (In this respect, Kant's God is more generic than Christian).
Clearly contemporary atheists and others show that this being socially evolved to believe in the uniformity of science and to have morality is possible without God. But that's not quite the same as proof that you can get to atheism without going through some sort of belief in God.
Turning to your alien example, let's say we find an alien society that does not believe in God. Since we are asking about a step in social evolution, that's not enough. We would then somehow need strong proof or sufficient evidence that they never did believe in a God.
On a separate note, Hegel believed that belief in God was a necessary step in social evolution -- a step which is superseded by realizing that we are God (or like God), because it turns out we are the thinking matter that is thought thinking itself. Many Hegel interpreters view the Hegelian project as atheistic for this reason. In the Hegelian system, God is a recurring posit we make when we don't yet have a better explanation, but God gets replaced when we do. To give a rough example of how this works in principle for Hegel (I don't have the text in front of me so I can't give you his text -- not that it would be easily comprehensible):
Step 1: we eat fish from the river
Step 2: we reflect and end up wondering why the river has all these tasty fish
Step 3: we become thankful for the supply of the river under the name of a god
Step 4: we realize that this is a pretty dumb idea and recognize that river supplies us according to a design
Step 5: we transition our God to the designer
Step 6: we imagine this designer as a thought thinking itself
Step 7: a human being takes up this thought about himself (Christ) and we realize this thought is for all of us (Spirit)
Step 8: we realize that we are the thought thinking itself and the other stuff was all our ideas
Step 9: we ditch the God part of the talk
This is what is normally called the "left Hegelian" interpretation (sketched down and oversimplified -- don't try this at home).