The problem is that any areas outside of what would later become the continental USA were also undergoing colonial development and European settlement themselves - or were already densly populated non-western areas like China, SE Asia, Africa, and Japan. Thus, it's hard to believe Indians could escape anywhere to develop on their own.
Mexico is probably the most likely option. It could be reached overland, was essentially a Native American/mestizo population anyway, and displaced American Indians would not suffer significant racism - at least not any more than the majority of Mexicans did under Spanish and Creole rule. I believe the Seminoles were not the only Indians to have some members flee to Mexico. However, Mexico was not necessarily a haven for aboriginal cultures. Spanish-speaking and conversion to Catholicism was pretty much expected. Elsewhere in latin America are also options for voluntary resettlement.
If you are talking about forced resettlement out of the future USA by US authorities - perhaps in league with other Europeans - the only place which seems empty enough (sorry native Australians) is the Melvin's favorite homeland. Of course, most of the country would not led itself to the horticultural practices of most eastern Indian groups - being generally dryer than Oklahoma - which itself semed to be a pretty awful place when the Five Nations were resettled here.
Here's a wierd Alternate TL along those lines: For some inexplicable reason the Brits and Yanks (or possibly the Yanks while they were still Brits and the Brits) decide on a massive program to resettle American Indians in Australia. Over the late 18th and early 19th Centuryundreds of thousands of Indians are setlled in eastern Australia, and give protection of the crown. Although missionized and nominally Christianized, they are provided general autonomy to organize their settlements as they wish. British establish forts to protect these people from aborigines and rogue white convicts settled there previously under an earlier silly scheme to use the place as a penal colony. Eventually Indian Australia assumes political self rule within the British Empire (which also hopefully still includes those American troublemakers).
Perhaps the best possibility would be for an early, voluntary exodus of people like the five nations, Iroqouis, and other more advanced farming groups to the eastern Plains and Mississippi valley area long before western settlement encroached in these areas, where they might perhaps set up quasi independent states and be better prepared to resist or negotiate better deals with the Americans as they eventually pushed westward. This would have required an ASB level of forseight and still might not have worked.