If I have understood your question correctly, you wish to know of examples of cultures that accepted the existence of gods other than their own?
Before the advent of Christianity, and even for a good while afterwards, this was the norm, at least in most areas. Cultures would meet, mingle and if the gods were similar enough (had similar domains) then they would assume it was the same god under a different name (See: Greek and Roman Pantheon) and merge them. Gods would bleed-through as people moved around and brought their gods with them.
It is possible, that these pantheons formed out of gods of different areas, with the more dominant tribe's god being perceived as the more powerful.
I think due to the polytheistic nature of many religions of the time - with thousands of gods, allowing for things like the Lares & Penates (household gods) that it was considered much more flexible.
Even the biblical religions arguably allowed for the existence of other gods, and that early Jewish culture was more henotheistic than monotheistic:
"Who is like you, O Lord, among the gods? Who is like you, majestic in holiness, awesome in glorious deeds, doing wonders?"
"for you shall worship no other god, for the Lord, whose name is Jealous, is a jealous God"
Even with active religions today, Buddhism allows for the existence of other gods (I think, my knowledge is not great in this area and would appreciate a confirmation from a Buddist)
'Free market' religion is not unusual in the scale of human history - the monopolistic religions of today are.