Even without going into PODS that alter the entire demographics of the continent before contact with white settlers, there are ways to avoid the Trail of Tears-- although this would not mean removing the oppression of Native Americans altogether (or even for the most part).
For my own TL, I recently investigated the quaint history of a US state that never came into being; Westsylvania. (Essentially a West Virginia that extended to include Pittsburgh.) One of the reasons the settlers there wanted to be a separate state as early as 1776 was that they were of the opinion that land speculators were making corrupt deals, driving natives off theit lands when settlers had no need for that land... and thus disturding the good relations the settlers enjoyed with large segments the Native population.
Apparently, this feeling was shared in many western settler communities. One imagines that, had the federal government cultivated those good relations and cracked down on corrupt land deals earlier, there would have been better relations with the Indian tribes across the board. Wealthy landowners hiring armed men to exterminate whole villages just so they could sell the land "free of Indians" probably didn't really help when it came to peaceful co-existence.
Needless to say, this wouldn't suddenly solve all problems, but it could help in improving relations. It would be a start. (I fully intend to explore the possibilities in my TL; it's too good to pass up.

)