In Bereishit, Hashem said to Adam
בזעת אפך תאכל לחם
This would seem to imply that bread is universal to all people.
We also know that bread has a particular definition: it has to be made from one of the five grains. Bentching after eating bread (כדי שביעה) is a Torah obligation, so this is a Torah level definition (at least according to the accepted halacha, Rabbi Akiva in Berachot 6:8 says you can bentch on any full meal).
But there have been cultures that didn't have bread. The Aboriginal Australians, before European contact, had something called bush bread, but it was made from plants other than the 5 grains, at least according to their standard identifications. Although there is a kind of barley native to North America, it seems that most Native Americans (again, pre-European contact) made their bread from other crops, like corn.
For havdala, and possibly for kiddush and other purposes, we can use חמר מדינה instead of wine. The Rashbam (Pesachim 107a) says another drink can become חמר מדינה if there is no real wine in the city; the Rambam is more lenient and says that if the people primarily drink something else instead of wine it becomes חמר מדינה.
Is there a similar concept of פת מדינה, in a place where there is no bread made from the 5 grains? Would you be able to bentch on this "bread", or make kiddush on it according to those who say that חמר מדינה works for kiddush?