Given the starkly different physical strengths between the genders, it's hard to believe that gender roles did not exist before agriculture.
Evidence of matriarchy includes living matriarchal societies (eg. the Mosuo people). I am no expert, though. If you look at Wikipedia's matriarchy page https://en.wikipedia.org/wiki/Matriarchy#Asia I actually live in Yunnan, which is smack bang in the middle of all of the Asian examples.
Archaeological evidence
Evidence from literate civilizations writing about their uncivilized neighbors, which goes back to the earliest known works
Evidence from writers encountering such societies up to the modern day, although they're almost extinct outside of the deep Amazon and the like.
Logical conclusions - without a food surplus, there is no class system and other results
Even hunter-gatherers have chiefs and elders.
Hunter-gatherer bands do not have chiefs. Looking at the Wikipedia article for "Tribal chief" it says "Historically, tribal societies represent an intermediate stage between the band society of the Paleolithic stage and civilization with centralized, super-regional government based in cities." I couldn't put it better.
Even with regards to Indian chiefs, and it's not hard to see how there are misconceptions about them if they're still referred to as "Indians", modern anthropology acknowledges that European notions about Indian bands and tribes in the 15th and 16th century were often wrong. Europeans saw parallels of European society in the New World which weren't there (of course there were different kinds of societies in the Americas, from Montezuma's Aztec empire, to humter gatherer bands).
That would make humans the only mammal out of ~5,500 species to not have a social hierarchy and those other species didn't develop hierarchies because they had a surplus of food.