Wherever a society exists, there is repeated exchange. And wherever there is repeated exchange, there are also markets.
(Of course, markets can vary in the degree of their development/functioning. One market may be better developed/functioning than another in that it has more frequent transactions, better enforced property rights and contracts, greater honesty/trust, lower transaction costs, greater competition, better flows of information, etc.)
Exchange should be understood broadly: It can be one tangible object for another or even a piece of information for another. It can also be gift exchange. (A common layperson error is to think that only exchanges involving money count as exchanges.)
Gift exchange includes instances where a hunter shares his big find with everyone in the group, with the tacit understanding that he has access to the group's other resources. It could also be where one group assists a second group, with the tacit understanding that the second group will provide assistance should the need arise.
Rough exchange ratios can be implicitly established and sustained through tradition: If lazy John is always skiving, then members of the community will notice and eventually sanction him (through e.g. ostracism). So, if John is consistently taking from the rest of the community $X$ amount of meat every month, then he must also contribute $Y$ in fruit or other goods and services monthly to the rest of the community, in order to avoid sanction. Over time, rough exchange ratios (and these may be a wide band) may form and be embedded in tradition. And if conditions change so that meat becomes more abundant/scarce relative to fruit, then the exchange ratios may change accordingly.
(There is also the evolutionary argument that these exchange ratios will tend to be "correct" in the sense that they correspond to actual scarcity: Groups that maintain the correct exchange ratios thrive, while those that don't die out. Groups that develop strong social norms to punish free-riders and reward appropriate levels of reciprocity thrive, while those that don't die out.)
If two isolated individuals each living on his own deserted island visits each other and engages in an isolated exchange once or twice in their lifetimes, then one could possibly argue that no market exists. But then one should also argue that these two individuals do not form a society (under any reasonable definition of the term "society").