Insisting that mankind always believe in god(s) is an ethnocentric view, seeing mankind only through one's own Abrahamic past (Judaism/Christianity/Islam). Lots of belief systems don't recognize concept of gods, only spirits (traditional Chinese, Azande people) or none at all (Piraha, Buddhism).
sources:
Durkheim's Elementary Forms of Religion, Asad's Genealogies of Religion