Or, to put it another way, have any societies ever developed without any religious beliefs?
Your title seems more of a Great Debate to me than a GQ. However the question in your post is presumably answerable and I would guess the answer is no. I don’t believe any society has developed devoid of religion (unless you get very small and very local).
Today I am not so certain that religion is necessary to the formation fo a society since we have codified laws that specify appropriate behavior. However, in ancient times it wasn’t so simple. Before codified laws it was religious belief that helped cement society together and keep the forces of anarchy at bay thus allowing societies to grow and prosper.
Also, I think it’s a particularly Indo-European sort of thing for religion to have become so separated from the rest of the culture that you could just swap yours out for a completely different one. I don’t think that many peoples viewed “religion” as so separate from the rest of their culture–their songs, stories, histories, myths, etc. It was just a way of looking at and describing the world, all of which were tied up in that culture. Only in the Indo-European world, I think, did “God” become this other thing whose nature you debated.
Sorry, that reads pretty weird, with all the IE stuff. My point: many “aboriginal” cultures (i.e., everything besides us “civilized” people…) don’t seem to make as much of a separation between spirituality, history, and popular culture as we do. So it would be as tough to remove that one thing (religion) as it would be to remove music or storytelling or the visual arts.
I can’t see any society developing very far without its members, individually or collectively, considering questions like “where do we come from and why are we here?” and “how ought we to behave?”. Speculating on these questions is going to produce a variety of answers, at least some of which are going to be “religious” in the sense we generally understand the word. So, no, I wouldn’t expect to see social development without some kind of religion emerging, and I can’t think of any counter-example.
I think this is a case where in theory a society could develop without religion – as long as the society has a common set of values, the presence/absense of a god to enforce those values is irrelevant.
But while that’s nice in theory, I don’t think we have a known example of this happening. Probably IMO because of some fundamental aspect of the human psyche that needs to invent imaginary invisible sky pixies to explain everything around them…
IMO indeed 
This question is a bit on the touchy-feely side for a straight factual answer, but then that is one of the joys of examining the human condition. IMO:
A pre-rational society also needs a method of spreading its worldview and standards of behavior to the populace at large. If a proto-society lacks such a cohesive force, its members will be open to being co-opted by other groups that do have unifying principles. Religion can serve in the creation of societies where rational discourse is unavailable, or just uninvented. I can’t think off hand of anything that would work under such conditions instead of religion. Big guys with swords, for example, would tend to be off-putting to outsiders.
Pretty much the first “specialist” that develops in a society, beyond a general “men usually hunt and women usually gather” sort of thing, is a shaman. I hate making overgeneralizations (because I’m invariably called on them), but I’d be very surprised to find a culture that doesn’t and never has used a mythology/religious worldview to answer some of the unanswerable questions.
Indo-European culture before the Enlightenment was pretty much inseparable from religion, too.