These views differ from tribe to tribe. In the Pacific Northwest, the various nations all have their own creation stories, and are often quite well aware of the creation stories of other nations. They accepted that the other nations' stories were true, just as their own were true. Many, perhaps a majority of the people I work with and talk with on a daily basis still believe this. Many believe that Europeans' have their own creation story, the biblical story (and that some other Europeans were the result of evolution apparently), and they accept that to be true as well. Europeans had the tower of Babel, but First Nations had the house of languages, and Europeans survived the flood in the ark and settled on Mount Ararat, while in BC at least, each nation and lineage knows the name of the mountain where their ancestors survived the flood waters.I know people who are pastors and also practice traditional medicine, because they don't see the ideas as being in conflict.

As to view of religion changing, yes of course. Many, possibly most, First Nations people are Christian, very likely a higher percentage than the general population. Aspects of traditional oral history were adjusted to fit a Christian worldview as presented by the learners. My own nation (Metis) practices a fusion of traditions, the result of a few centuries of change, to the point where when I say "nehiyawi-ayamihewin - Cree Religion - it means our flavour of catholicism, and when I say "moniyawi-ayamihewin - white-man religion, it means protestantism, at least for most Cree speakers. It's important to note that what I have described would not be considered religion or religious by Native Americans by and large, it's just reality, there's nothing religious about it.

Finally, I'll say that almost all Native Americans and First Nations peoples are creationists, in that they take it as a given that the world was created by the creator, in a variety of means. Many traditions already have names for a creator, for his son, for his servants, and these terms were co-opted into Christianity, and long after much of Christianity will have rejected creationism, Indigenous Christians will still be strong believers.

Now as to sources, I like the following two:

Ah-ayitaw ekikiskeyihtahkik maskihki ohci - they knew both sides of the medicine - edited by Freda Ahenakew.

Bella Coola Myths, by Franz Boas.

I cannot speak for all natives. However, I can offer you the view of my tribe. But please note that a lot of my words are the traditions of my tribe. While I can source some of it, I cannot source all of it. I will try to avoid being anecdotal.

I am from the Nez Perce. My tribes creation story centers around all of man coming from nature, coming from wolves that were created by the Great Spirit. That, of course, being the bottom line of it.

During the 1800's, many tribes started to adopt different religious views as contact with Europeans/Americans became more prevalent. These religious movements often came up with new explanations for the "white man" and were meant to give hope to natives that they would soon disappear, whether by force or by nature. An example would be the Ghost Dance and Wáashat. My tribe, in the past and currently, adopted and believed in Wáashat. In this religion, followers were promised that they would be delivered from their oppressors if they stuck to their traditional ways and nature would be the means by which the settlers were removed. This faith peaked around the mid-nineteenth century.

However, Chief Joseph gives more insight on this matter. He is quoted as saying "All men were made by the same Great Spirit Chief."

Chief Joseph gave this quote in 1879, according to that article. This would have been far after the first meetings with the settlers and the adoption of Wáashat. However, his quote demonstrates that he believed all men, including the settlers, were created by the Great Spirit. His father, known as "Joseph the Elder", was baptized as a Christian and was given the name "Joseph", which was passed down to Chief Joseph, or 'Young Joseph'. This means that it is very likely Chief Joseph held traditional views, as well as views centered on Christianity. This is the case with many natives today, as /u/Muskwatch brought out.

In fact, many native tribes adjusted their beliefs in order to accommodate for Christianity. This happened because natives were not allowed to practice their traditional beliefs, such as the ones who were sent to boarding schools. Some even make the case that the "Great Spirit" belief, obviously harmonizing with the Christian God, was created as such an accommodation.

So in short, it is difficult to answer your question, at least for me. It depends on the tribe, their cultural/religious traditions pre-Columbian era, and the religion/movement they subscribe to in order to see how Native Americans view Europeans in a religious context. Some tribes didn't have an explanation, some thought they were created by the Great Spirit, some thought they even came from nature as well.

Some believed they were the same origin, such as Chief Joseph. Some believed they were a different breed. In many cases, probably all, natives personal views of religion did change as a result of meeting colonists to some extent. And as for if there was a general consensus, it really depended on what area of the country (speaking of the U.S.) you were in. Wáashat was practiced primarily in the Pacific Northwest and the Columbia Plateau. Other areas, such as the East and Midwest, stuck to the Ghost Dance. The Southwest stuck with the Peyote Religion. Tribes in these areas, while they might've had their own tribal traditions, shared some similar beliefs and participated in the movements that swept through their areas.

Again, though, I want to note that your question is specifically about the religious beliefs of Native Americans. Many tribes, especially in the past, did not document their traditional religious views, for they were passed down orally and within the tribe. Some things concerning faiths have been published and explained now in written form, but they are not always accurate. What I provided as sources is mainly just to establish the claims I've proposed and to suffice if anyone were to ask questions. The material used for what I sourced is as follows:

Chester Anders Fee, Chief Joseph: The Biography of a Great Indian, Wilson-Erickson, 1936

Hunn, Eugene S. 1990. Nch'i-Wana, "the Big River": Mid-Columbia Indians and Their Land.

Relander, Click. 1956. Drummers and Dreamers.

Ruby, Robert, and John A. Brown. 1989. Dreamer Prophets of the Columbia Plateau: Smohalla and Skolaskin.

Edit: Grammar

From your question, I'm assuming you're thinking something along the lines of Hernán Cortés and the theory that the Aztecs believed him to be Quetzalcoatl. Someone more familiar with mesoamerica can talk to you about that.

In reality, word of European contact spread much, much faster than Europeans themselves. Trade goods, especially iron goods, are almost always found before the arrival of Europeans throughout North America. Word of Europeans spread along with their goods, and so (at least in my area), people had an idea of the source of these goods before they met traders and explorers themselves. You'll want to ask someone who specializes in the East Coast of North America, the Caribbean or elsewhere, where first contact was much more of an abrupt thing.

The lack of written records makes establishing Native viewpoints difficult, and oral histories tend to survive in fragmentary format only, given the American and British/Canadian attempts to literally beat foreign language out of Native Americans.

Here's an excerpt from A Journal of Captain Cook's Last Voyage to the Pacific Ocean by John Ledyard, covering a trip to Unalaska Island in October 1778:

I was surprised at the behaviour of the Indians, for though they were curious to see me, yet they did not express that extraordinary curiosity that would be expected had they never seen an European before, and I was glad to perceive it, as it was an evidence in favor of what I wished to find true viz, that there were Europeans now among them.

Now, Ledyard's experience was somewhat interesting, because it's a European coming across Alaska Natives who were well familiar with Russians already. What about Natives who were unfamiliar with Europeans already? For that, let's turn to the journal of Jean-François de Galaup, comte de Lapérouse, who visited Alaska in 1786. Lapérouse's crew stopped in Lituya Bay, a place not explored by Cook. It also does not appear in Russian charts of this period, making it unlikely that the Russians had physically visited. The Spanish would not mount their first expedition to the area for another two years.

Among the Tlingit of Lituya Bay, Lapérouse found iron tools, possibly "from the Russians, or the factors for the Hudson's Bay company or from the American traders who travelled into the interior of America, or even from the Spaniards; but I shall hereafter make it appear, that it is most probable they procured these metals from the Russians."

But you're not interested in tools. You're interested in contact and religious ceremonies. Here's what happened when Lapérouse welcomed some of the Tlingit leaders aboard his ship:

On the day of our arrival we were visited by the chief of the principal village.

Before he came on board he seemed to address a prayer to the sun; he afterwards made us a long speech, which was terminated by some very agreeable songs, that bore a strong resemblance to the plain-song of our churches; the Indians of his canoe accompanied him by repeating the same air in chorus. After this ceremony, they almost all of them came on board, and during the space of an hour danced to the sound of their own voices, which was very much in tune. I made the chief several presents, which rendered him so troublesome that he every day passed five or six hours on board, and I was obliged to renew them every frequently or else he went away discontented, and muttering threats, which however were not every dangerous.