What is the title? I would be interested in reading it.
As for your ideas. I would suggest checking out my TL for an idea. Sorry of the plug. As to how it could happen in the 1820s, I would say that is too late. I think you would want Washington to take an early and strong stand on Indian Affairs something he did not do. War Secretary Henry Knox had an idea of ringing most of the Cherokee towns with a series of forts to protect the Cherokee from Settlers. It was scrapped for being to expensive. Somehow make that plan more feasible and alleviate some of the land pressures that exist in the South and you may have something. For instance, no Cotton Gin makes the expansion of Cotton production less likely and combined with a more stable European situation (I.E. Napoleon is defeated early, Louis XVI launches a successful counter coup, etc, something to elimate the near 20 years of European war) and you ease the pressure on the land issue. Maybe enough to give the idea of a "Cherokee/other one of the 5 tribes State" some room to grow in policy makers' minds.
As to racism, there were just as many out and out racists as their where people who had respect for the Native American, so I don't think that is that big of a problem, a problem yes but insurmountable? No. I base this on the comments of many of the Founders on Native Americans and their rights as well as the experiences and research into characters like Daniel Boone, Davy Crockett, Sam Houston, and many others. So to assume that every settler and colonist was an out and out bigot, is wrong but to assume them totally innocent is also wrong. I think the racist feelings of the settlers was one of those things that is butterfly-able as much as anything. Take the Delaware Treaty of 1779, if White Eyes isn't killed by Frontiersmen and Congress takes Indian demands seriously then I think it is possible.
I think once you hit about 1820 the chances of anything much different from OTL are much too slim. At that point American Govt. policy towards Indians was basically in written stone and unlikely to change. While Jackson does receive a lot of the blame for Removal and rightly so. To say that without him it wouldn't happen is ridiculous. The pressure on the frontier was already building and all of the other candidates in 1824 and 1828 had endorsed Indian removal or in Adams' case, who came up with his own plan (in 1828). I think you need to attack Indian Policy early and stick with it. That is the only chance to create what Eckener is looking for.