Your questions are a bit complex and loaded, so bear with me.
Religion as a concept is difficult to define and doesn't really have a conclusive answer as of yet. There are societies that do not have a word for religion:
Many religions do not feature a deity and may feature more incorporeal elements associated with it. Consider many eastern religious practices such as Shinto, Taoism, Confucianism, or Buddhism. Buddha is a central figure, but can one say he is a deity? Did he create the universe? There is an error of definition when we consider only the Abrahamic faiths as constituting 'religion'.
God as a concept is even less well defined. Sometimes described as ineffable, the Eastern Orthodox Church attempts to describe aspects of God by what He is not rather than what He is because of this. There has never been, nor likely ever will be a consensus on the matter.
The word 'non-believer' is just a reference for labeling those that do not adhere to one's particular denomination and hence is dependent upon the context of that particular denomination's orthodoxy. They each have their own beliefs regarding such issues, such as how our ancestors and prehistoric peoples' relationship to Christ before his arrival might be.
Spirituality, or religious beliefs, seem to go far back in prehistory. There is speculation that Neanderthals had spiritual beliefs regarding the afterlife due to possible
evidence of burials and burial goods.