I've written about this previously on the sub in these two posts:

How much is western colonialism responsible for the introduction of the gender binary in most modern societies?

2 Spirits in native american culture, what was it about?

As you will see by reading the above, your supposition that there is little historical evidence for queer gender identities in Native American cultures really couldn't be more incorrect. There is ample scholarship about the many specific identities and their cultural contexts - just because you are not familiar with them does not mean they do not exist.

To help with finding sourced material on the subject, I'd like to contribute my small collection of references. Note: a lot of the ethnographic sources use the term "berdache", this is now widely considered to be a slur and is not preferred terminology. Also, a lot of this material is from the late 1800s and early 1900s, when many academics had less-than-charitable views on gender variance, so there are sometimes unsavory opinions, problematic stereotypes and such.

• In Anne Smith's Ethnography of the Northern Utes, the author notes that one informant, Augusai, was a berdache.

• Robert H. Lowie's 1924 Shoshonean Ethnography has a section on "berdaches":

A Shivwits informant recollected hearing people speak of a man who never hunted and though not dressing like a woman acted like one and had a feminine voice. He would lead the women with a basket when they went seed-gathering and roasted seeds like them. He was married to two men, sleeping with each on alternate night. In myths such persons are called ma+ai'pots.

Among the Southern Ute Panayus remembered hearing his father tell of a berdache (tuwasawits), who owned a great many horses.

At Ouray my informant saw two berdaches himself, and my interpreter Tony recalled one he had seen there about eighteen years ago, - a tall stout man, also another one of short stature at Whiterocks.

• In Hernando Alarcon's 1540 voyage up the Colorado river, which you can read here from the Journal of California and Great Basin Anthropology, on page 16 he relates that, at a site some distance up the river:

There were among these Indians three or four men in women's apparel.

• Isabel T. Kelly, 1939 Southern Paiute Shamanism on the Las Vegas band, notes:

Among them, shamans (puaxanti) were of either sex, but women shamans were considered almost without exception malevolent. A berdache dreamed of changing his sex, by my informant did not know if one ever became a shaman.

• Julian H. Steward's 1933 Ethnography of the Owens Valley Paiute on p. 238 (in University of California Publications in American Archaeology and Ethnology Volume 33. No. 3) says:

Berdachism is called tudayap, "dress like other sex." One such man dressed like a woman, associated with females, and did woman's work, washing for the white people, and did not marry; but he had no other abnormality. A young boy dressed like a girl, went to a girls' dormitory in a Nevada school, was put into the boys' dormitory, then put out of school, married a boy who was granted a divorce when the judge learned the facts. He is probably in Nevada now. Berdaches were not shamans.

• Lynn Gamble in The Chumash World at European Contact says on p 178:

Women, and men who adopted women's gender roles, played an important role in feasting and subsistence activities.

And on p 218:

Gender cannot be fully investigated without recognizing the significance of two-spirits (berdaches), who played an important role in Chumash society and who possessed considerable power in the role as 'aqi or undertakers.

... Holliman (2000:181-182) suggests that the individuals that served as 'aqi were sexually non-procreative, and could be considered a third gender composed of post-menopausal women and biological males who adopted women's attire and work.

• Sandra Hollimon, 2001, "The gendered peopling of North America: Addressing the antiquity of systems of multiple genders", chapter 8 of Neil Price's The Archaeology of Shamanism, makes a case for a "broad cultural continuity across much of the circumpolar region" which includes a system of multiple gender common to many North American societies, associating gender "difference" with supernatural power.

• Traci Arden, 2008 is a good review paper, "Studies of Gender in the Prehispanic Americas"

Then I've got a bunch of random stuff:

• Evelyn Blackwood, 1984 "Sexuality and Gender in Certain Native American Tribes: The Case of Cross-Gender Females"

• Gabriel Estrada, 2011 "Two Spirits, Nadleeh, and LGBTQ2 Navajo Gaze"

• Waldemar Kuligowski, 2005 "The Third Sex - Lesbianism and Transgender in the Indigenous Cultures of North America"

• Sandra Faiman-Silva, 2011, "Anthropologists and Two Spirit People: Building Bridges and Sharing Knowledge"

• Pruden and Edmo, "Two-Spirit People: Sex, Gender and Sexuality in Historic and Contemporary Native America" presentation slides, but has a lot of info on linguistic terminology, and a nice section on historic two-spirit figures

• Max Carocci, 2009 "Visualizing Gender Variability in Plains Indian Pictographic Art"

(edit: I clearly have no idea how to correctly format a reddit post anymore, please excuse the mangled formatting)

I think you have answered your own question...."Native American history can be very challenging to study as it can skewed by colonial accounts as well as the limited access of oral traditions..."

I would add that most accounts - historians, anthropologists, and all other non-native - are "traditionally" very biased and reflect points of view that see "others" through the lens of the observer, outsider, and serve often to reproduce misunderstandings and mistakes in interpretations of peoples and cultures experiences, expectations, and systems - especially when they are in tension with the observers understandings. (Noting as well that the recognition of ethnocentric analysis is now being acknowledge more often and considered as more contemporary scholars re-read the past.) In the case of "gender-fluidity" in NA cultural groups, we must remember that "gender fluidity" may have meant something very different to NA people in the past (and today) - before settler imposition/expectations/oppression - and thus has been missed/unseen because of these ethnocentric hegemonic discourse and the push to reimagine NA's into a particular narrative...while NA people have had to protect themselves and their culture against complete assimilation and erasure.

Further "oral traditions" are not outsiders to have and use, and while they may shed light on many things - these are not everyones to pick apart... And to look at them through colonial eyes (read all outsiders) often misses what these stories are telling.

The job, our job, now is to work to understand the past, and the ways in which different cultures (read non-Eurocentric, white, settler colonial) may have considered "gender" and to remind ourselves that "gender" - its performance and how we read it - is culturally constructed as well. Only then can we begin to "see" differences and understand the complexity of human identities across cultures and back into the past. And maybe, just maybe we (settlers) don't have all the answers - or understand differences through other lenses of culture. We need to listen and respect... and not expect to be the authority.