Can one innovator really show that it works better? Especially back before agriculture got started, and hence before we started breeding plants that were well adapted to human needs. E.g., a lot of agriculture now is based on wheat, but wheat was a much less effective food plant before human intervention.

Almost by definition, "more complicated culture and a structured society" isn't a thing one person can try out on their own and demonstrate the superiority of. Probably some individual interventions along the path are, but I don't think we know that "pre-colonial indigenous people" didn't try any of them. (Do we?) And even those individual interventions -- if one of them produces (say) more fruit but at the cost of catching fewer deer, would it have been obvious whether it was a win?