I know there was no writing (is that correct?), but did any North American tribes have oral histories that they later wrote down? Or are there other ways we might know what was happening politically in the century or two before Europeans arrived and brought plagues (which, I think I'm correct in saying, severely disrupted the political situation?). For example, artwork about famous leaders?
As opposed to say, what kind of pottery they used or whether they were farmers or hunter-gatherers, which presumably you can find out reasonably easily via archeology.
So there are three components here. There are oral traditions that recount political occurrences prior to European colonization, and I'll share one from the U.S. Southwest. /u/Reedstilt might be inclined to share some from the Southeast. Secondly, while you dismiss "what kind of pottery they use" as evidence that can be brought to bear on this topic, archaeologists very often try and reconstruct political structures and events using such marginal evidence as pottery and I'll go through how that's done. Finally, I'll cover that map.
In southern Arizona (roughly Phoenix/Tucson), two O'odham informants recorded a version of their origin story in the 1930s that has several interesting implications for both the archaeological record of the region and reconstructing political events. The O'odham are the modern Native American inhabitants of the Phoenix and Tucson basins, but we have to understand the story in the context of the archaeological history of these places. The majority of the text concerns the "Hohokam", the name applied to the pre-Hispanic inhabitants of southern Arizona that constructed the great houses, ball courts, and canal systems the region is famous for.
Importantly, the archaeological evidence suggests that between about A.D.500 when we first see what we could call Hohokam culture up to around A.D.1450 when we see a disappearance of that culture and it's replacement by something much similar to historic O'odham cultures, the Hohokam world became significantly more hierarchical. What starts off as a fairly egalitarian society had by A.D.1450 begun to look quite hierarchical, to the point we can reasonably discuss the existence of chiefs or other such elites.
How this relates to the story related in the 1930s is that much of the story concerns warfare against the "bitter" chiefs in their great houses by those who would eventually become the O'odham. There are cosmological and theological overtones to the story, with it framed as the O'odham ancestors enacting vengeance against the great Hohokam chiefs because of their failings in killing their god. Despite that, the events recounted do seem to map pretty accurately onto historical occurrences. The geographic extent of the story, and the great houses mentioned, maps fairly well onto known archaeological sites, particularly Casa Grande (already shared above as an example of a great house). This also maps onto the rest of our archaeological understanding of both increased hierarchy in the last 1-2 centuries of the Hohokam (ca. A.D.1300-1450) and increased conflict and possibly warfare at the same time.
While the details of the story don't necessarily map exactly onto historical events, the general arch of the story - the overthrow of elite, big house nobles or chiefs and the social order they maintained in favor of a much more egalitarian social order that persisted up into the Spanish period - does very much correspond with the archaeological knowledge we have.
However, we have to scrutinize oral histories just as much as we scrutinize the documentary record. Importantly, Bahr (in the Short Swift Time of Gods on Earth) is quick to point out that the 1930s oral history is significantly different from two similar histories recorded in the 17th and 18th century. This is particularly in regards how prominently the great houses and their violent overthrow feature in the 1930s text, but not in the colonial period texts that are closer to the actual events. While the same kind of conflict is present in the earlier texts, the "grand territorial sweep" (as Bahr calls it) of conquest and conflict isn't present, and rather is scaled down considerably in spatial scope.
That said, and Bahr agrees, I think it is fair to suggest that the idea of conflict between the O'odham and these elite, hierarchical great house (or perhaps just one great house) reflects some actual historical event. This event would, very broadly, be the active rejection (perhaps violently) of the increasingly hierarchical Hohokam system and the turn towards the smaller scale, more egalitarian O'odham social organization witnessed in the Spanish period.
This bring me to the second point, that archaeological evidence can actually do quite a bit to tell us about politics without written records, even using such innocuous evidence as pottery. The easiest thing to establish (usually) is what kind of social organization we are looking it. Are there elites in a highly stratified social system, or are is the system more egalitarian? Is the system highly centralized or highly decentralized? For the first question, we can look at different lines of evidence to establish whether or not we see a heterogenous or homogenous distribution of goods throughout a community. The more hierarchical a community, the more we typically expect to see a heterogenous distribution of goods. In other words, a palace with more and/or rare stuff compared with the typical household in a community. Likewise with burials, were elite burials typically have more and/or rarer burial goods included than your typical burial, and they also often have more elaborate burial contexts in terms of architecture (e.g. a pyramid instead of just a regular grave).
We see this kind of evidence archaeologically in the Hohokam example. Around A.D.500 we are talking about villages of pithouses that may have a small plaza and wherein some houses are slightly larger than others, but otherwise there is a very homogenous distribution of goods and architecture. However, over time we see increasingly differentiated architecture (bigger and bigger pit houses until we end up with huge platform mounds and great houses) and some unequal distribution of goods, but to a much lesser degree than the inequality in architecture. Perhaps the best example is the crypt in Casa Grande Ruins, which is quite possibly the richest burial in the Southwest with a "sarcophagus" and what has been called a throne.
Likewise, we see a fairly rapid decrease in the complexity and hierarchy of societies in southern Arizona in less than a century between A.D. 1400 and 1500. It seems like there was a very conscious rejection of the existing social hierarchy in this time period, perhaps aided by environmental factors and increased warfare.
In terms of centralized or decentralized systems, we can compare archaeological sites against each other and look at a few factors to establish what kind of regional systems we are looking at. For example, we can get pretty good archaeological data on how the production of goods was structured (e.g. specialized production centers, redistribution via a "capital", or whatever other organization you can think of). This then tells us something about how different settlements related to each other politically. The elaboration of elite architecture at certain sites can help us establish if there is a regional hierarchy of not (e.g. a palace at a capital, and maybe smaller administrative structures at second-tier sites, while small hamlets have no architecture of that sort).
Now, archaeologically is typically very bad at getting at individual events that occurred (unless we have the luxury of a site like Pompeii) and so has to look at larger time scales and societies as a whole, but that doesn't mean we can't use archaeological evidence to discuss political organization quite extensively. We can't always pinpoint individual events (like the conquests of the great houses in the O'odham story I began this discussion with), but we can see some general political trends and changes that do tell a story. In the Hohokam case we see the gradual increase in social hierarchy over almost a millenium followed by the fairly rapid collapse of that hierarchy into a very different kind of social organization.
Finally, the map: it is a very poor. On the broadest scale it has some value, but it has so many issues I wouldn't bother using it for anything. Instead, this map (despite having some issues) is much more in line with what North America actually looked like. While not having as much detail, this is a fairly alright map of the different culture areas archaeologists typically break up pre-Hispanic North America into (though I should stress that the Southwest is unreasonably large).
Source:
Bahr, Donald, Juan Smith, William Smith Allison, and Julian Hayden. 1994. The Short, Swift Time of Gods on Earth: The Hohokam Chronicles. Berkeley: University of California Press
As a slight follow-up, an American website for kids learning history (I'm not American, so only studied American history for 1 hour in university), showed me this map, is it accurate? Rubbish? Sort-of correct but reductive? https://www.learner.org/interactives/historymap/images/new_map.jpg
