You need to eliminate Protestantism.
Like almost every poisonous social meme within American life, our treatment of the natives comes almost directly from the attitudes of our Puritan and other-Proddy forebears. These Protestants, lacking in the insititutional heritage, traditionalism, bureaucracy and Jesuits of the Catholic Church, turned instead to the Old Testament for inspiration.
This turn towards the Old Testament was not just a phenomenon in the US; South African Boers, themselves Calvinists, had the same religiously motivated rhetoric towards the animist tribes as we did towards natives.
These hardscrabble settlers on the frontier, of all denominations, found an easy theology in the story of Israel. All the land they were finding was given to them by God, and the Israelites had to clear the Canaanites out of the land of Israel. Thusly, the various native tribes were made into Amalekites, savages, ungodly peoples meant to be destroyed in God's name. Add to this the typical economic arguments--settlers need good land, full settlements vs. semi-nomadic life, and you have a very volatile situation. Add in the fact that these settlers had long memories of the earliest Indian wars, which were in their time existential conflicts for the early colonies (King Philips War, the Powhatan War... all could have gone south for the colonists, and we could have seen these settlements exterminated themselves) and you have the perfect mix of motives, history, fear and God to engineer within the settlers a call to exterminate the native.
Even the European immigrants inherited this mindset; I don't recall too many Catholics out in the Midwest, but I do recall a lot of Protestants...
Now, Catholics on the ground could be just as bad; the slave raids into the Brazilian jungle, the destruction of Mesoamerica, the encomiendas, etc. What Catholicism had was the institutional control to at least have some Jesuit missions (like those in Paraguay), Jesuit conversions, and, at least on paper, laws against slavery and mistreatment of the Indians (which were totally ignored in the New World; materialism trumps whatever New Laws de las Casas lobbied for).
Other Protestant memes include literalism--which is why all these modern fundies quote Leviticus on homosexuality rather than Christ--and the Protestant work ethic, which itself tied into the idea that settlers, if they worked hard enough, would be given this God-sanctioned land, which they needed to clear of settlers.
The more "conscientious" argued for boarding schools to assimilate people. These were run terribly, and so we had even more of a death toll. Now, I don't see America being able to coexist well with semi-nomadic native tribes, or even with settled tribes (the Cherokee), but if we could have more Sequoyahs willing to settle down--and a SCOTUS case or two recognizing some land rights--we might be able to prevent the worst of the abuses. I really don't see the settlers up and becoming decent towards the natives, but there is room to make them better than they were.