Killing Andrew Jackson during War of 1812 would help bit. Without him there is chances for bit better times for natives altough it is still not going to be great.
I don't think killing Andrew Jackson would actually help much. Jackson himself believed that the Indian Removal Act was necessary to prevent the Cherokee from being massacred in Georgia.
"Jackson might claim his policy was liberal, but that claim didn't make it so. He held out the alternative that the Cherokees might remain in Georgia by submitting to the authority of the state and living like whites. But considering how far the Cherokees had adopted white ways and how little their efforts had won them of respect from their neighbors, such a response would have required a daunting leap of faith. The harsh fact of the matter was that Georgia was determined to expel the Cherokees and take their land. Jackson knew this, and he refused to prevent it.
He was on firmer ground in declaring his policy inescapable. The defenders of the Cherokees were few and mostly far away from Georgia; their persecutors were many and near at hand. Given the racist realities of the time, Jackson was almost certainly correct in contending that for the Cherokees to remain in Georgia risked their extinction. To preserve the Cherokees as a tribe-to enforce Marshall's decision-would have required raising and sending federal troops to Georgia, stationing them there indefinitely, and ordering them to shoot white Georgians who threatened the Indians. Jackson realized that American democracy simply wouldn't sustain such a policy. It was one thing to threaten to use force to preserve the Union; in such an endeavor he could expect broad support from the people who would actually do the fighting. It was another thing to ask white citizens to risk death protecting Indians. They wouldn't do it."
-Andrew Jackson, His Life and Times: pgs. 492-493, H.W. Brands
Thus to actually protect the Native American tribes in the southeast, it's not enough simply to have a president that won't support the Indian Removal Act. Instead you need a president that will actually send federal troops into Georgia to protect the Native American population. I don't know if there is any plausible US president at that time that would be willing to do that.
Perhaps best would be if USA loses ARW and Brits remain there. Then there might be better treatment.
Maybe, though unless the British are willing to station enough troops on the frontier to keep American settlers from going west, I think you are still going to get a steady stream of settlers invading Native American land. And of course if the British do seriously enforce restrictions on western settlement that is going to create a lot of resentment in the American colonies. If the British end up having to face the choice between risking a second American Revolution or selling out the Native Americans, they will probably choose the later option.