But that was only possible because the greater part of VA was unrepresented in the Unionist legislature at Wheeling.
With the war over, any legislature would presumably be elected by the whole State, and how keen would even a "Black and Tan" legislature have been? After all, if you create a majority-black state, you are in the nature of things also creating a majority-white one next door to it - thus giving KKK raiders a refuge to duck into after doing their business. And, as previously noted, even substantial black majorities in MS and SC did not prevent "redemption" there, once the North got fed up with continually having to send in the troops.
The example of Virginia and West Virginia demonstrates what the Union can get away with
during the Civil War.
Indeed if they wait until the war is over, there would be little choice but to allow the entire pre-secession enfranchised white male population of each state to vote, minus perhaps persons with such rights suspended due to participation in the secession or Confederate state at a high level--it would hardly be practical to disenfranchise every Confederate or Confederate-siding state militia soldier. Even if civil suspension of rights went as low as every commissioned officer though the electorate, even adding in every freedman, would probably be essentially the prewar voters plus the freedmen--it could be that in some of these states universal manhood suffrage would change it a lot, but is there any guarantee adding in poor white men previously left out would tip the balance? Even with all the freed African Americans pretty certain to vote Republican and certainly support these state scrambling schemes?
But...during the war, opportunity beckons. Tell me, do you regard what Lincoln did with separating West Virginia from Virginia as legitimate or not?
I do.
He, and the western Virginians, were playing fast and loose with normal due process of course. But the reason they could do that was because the champions of causes these western Virginians opposed chose to opt out of US due process, to take their marbles and go home now that they were in danger of starting to lose a game they had been winning. That's the smart time to leave a poker game or a craps table, but the USA was not supposed to be a gambler's den, it was supposed to be a covenant to accomplish the purposes laid out in the Preamble to the Constitution. In particular the secessionists objected to the idea they might be asked to follow through on the last clause, "...secure the blessings of liberty to ourselves and our posterity."
So to be pedantic about it, the western Virginians technically should have had no right to unilaterally secede from the state of Virginia without the consent of the rest of Virginia. But the secessionists of Virginia, who pretty well overlapped the class of people who had hitherto dominated all Virginia as a ruling minority elite, were responsible for the Wheeling Convention being unable to draw a fair share of citizen representatives from all over Virginia! It remains somewhat sophistical to suggest maybe a truly democratic Virginia representation might have granted the separation of WV freely; you know and I know and they knew they probably would not. But it is I think fair to say that these pro-mountain zone separation and pro-Union elements in Virginia, and their Union-Republican allies in the Federal Government, had nevertheless a legitimate opportunity to cut through the red tape and deadwood of an established Constitutional order, the silver lining to the dark cloud of secession and civil war. It was the Confederates who muddied the waters of what was and was not proper due process, and created both impediment of regular due process and an emergency urgency justifying taking action. Lincoln once responded to the suggestion he should be confident God was on his side by remarking he just hoped he was on God's side. I think God's side in this was clear!
So--the opportunity was a general thing. Part of what justified Lincoln and the Republican dominated Congress was that separation from Virginia was what the western Virginians had wanted for a long time. But more fundamentally, Lincoln understood that no form of government was an independent entity existing on its own; all were instituted by human beings to serve their more or less legitimate purposes of combined action in pursuit of both general welfare and general rights. In privileging the Union, the Federal power, over states he dissented (perhaps; everything he did in that direction could be both explained and justified as wartime expedient) with the people who obsess over the notion the states are primary. But fundamentally, all government at both levels exist to provide as he so economically and resoundingly put it, government "of the people, by the people, for the people." We can agonize over whether our devised Constitutional structure would allow us to readjust the state boundaries today or not. But at the level of the fundamentals, the states exist to serve the people who live in them. The Abolitionists included in that number the people of color a pro-slavery SCOTUS ruling had just said should not count, of course. The Unionists had long term concerns about viability. The secessionists had shot the moral foundations of their own pretensions to rule completely out from under themselves.
Therefore if the Union forces were able to seize small, token bits of a state in secession--that is, per Lincoln, with its normal state government machinery usurped and rendered useless for normal due process thanks to a criminal conspiracy in plain violation of the interests of "of the people, for the people, by the people," it would be a reasonable option to foster a convention of the people in the liberated zone, and ask them to solemnly consider forming new states with new boundaries. The fact that the slaver interest would not be "fairly" represented would be entirely down to the slavers having overreached and arrogated control of the whole bag of marbles all to themselves. Agreements to create separate mostly white versus African American states in this rearrangement would probably get the vote of African Americans recently liberated! As for the "white" people, I think separating out the slaver interest for the most part, non-slave-owning whites would agree they are better off in a separate state.
To address the other issues you bring, namely "what is to stop the Redeemers from triumphing as they did in South Carolina or Mississippi OTL anyway?"
South Carolina is indeed a chilling example! But I will suggest it makes a difference whether the Union accepted and encouraged the mobilization of the African American subject classes as a people in their general war tactics or not; if the rising slaves were a part of the Union assault on Confederate/secessionist institutions, they are in a stronger position after the war. Meanwhile, in the OTL situation without redrawing the boundaries, many conditional supporters of freedman's rights and interests had qualms about these ever overriding or inconveniencing "white" people. But if Union armies advancing with the aid of rebelling slaves are carrying out in part the enforcement of new African-majority state governments formed from the smaller earlier liberated zones, they can stop expanding the freedman states when they reach the boundaries beyond which it would start becoming a white majority state. Whites "trapped" within those boundaries are actually free to go, to migrate beyond the border to complementary white-majority states. So--the freedman state governments would have a much freer hand to exercise state powers forthrightly in the interest of the majority.
One interest generally shared by both dominant majorities and most people in some opposition to that majority is Law And Order. The Redeemers were able to terrorize and repress African Americans because of a faithless state government regime that turned a selective blind eye to gross violations of public peace, conniving by inaction as much as by direct action in repressing a significant part of the people they were supposed, to be legitimate in Lincoln's distillation of the definition of a democratic republic, "of, by, and for."
If most African Americans now live in black-majority states (and just as disgruntled whites may leave these states, so too at least of those blacks trapped in the white majority states can also migrate to the nearest AA majority states, their state and local governments now exist of, by, and for
them. It was a common cry against Reconstruction and especially in the Orwellian whitewashing of the Redeemers and their purposes and accomplishments in later generations that freed slaves given such power would abuse it grossly, to turn the tables on whites and treat them as unjustly as the whites had hitherto treated the blacks. But claims that such things actually happened on any large scale were quite mendacious. The situation is not totally symmetric! Indeed if in say 1867 the occupying Union forces and the entire North were to vanish from the Earth there would be some temptation in the new white majority states to conquer and partition the black-majority states, and relative poverty in the latter would mean they might be ill able to resist an all out drive for conquest. But even then, it would hardly be a slam dunk! Giving most African American people defensible borders they control the defenses of allows them to collectivize and concentrate their best efforts, and I think given simple freedom and a handful of months to enjoy it, and freedom to acquire weapons and organization of their own, they could have made a good account of themselves.
But even with minimal commitment to civil rights or the interest of African Americans, as long as the various states are in the Union, all out wars of conquest of one by another are not an option. Accordingly you spoke of the same tactics used by white supremacists OTL.
I hope it is pretty plain by now why that would not work the way it did in the old state boundaries OTL. As a general rule, African American populations could not rely on the formal state structure to even-handedly defend their interests the way these same authorities would protect white populations from the same sorts of violation. Even if they could say elect a sheriff or three, these men would be vulnerable to selective targeting by the white supremacists; the prosecution of their murders would be in the hands of a white-run police and court system that could, if sufficiently corrupted, give aid and comfort to the culprits.
If however we have states where freedmen dominate electorally, then we can be sure those states can and will use state powers to fully protect to the extent of their ability African American populations and individuals from the depredations of such terrorists. Murdering one black sheriff will just result in all his deputies, including the one promoted to acting sheriff, and the entire state police apparatus, in a manhunt for the murderers, and if caught they are going to jail, and going to face a
fair trial with a largely black jury and probably a black judge. As noted, former slaves might or might not wish to turn the tables and indulge in gross discrimination against whites, but first of all I think few of them would really want to, and regardless of their possible vengeful or petty desires, they know they are on a national scale a not yet much respected minority, and while they might not be able to count on Northern Republicans to come running to their aid every time they get a little hurt, if they are respected at least a little the north will at least support their own state due process...but if they lose that respect and are plainly indulging in black-supremacist outrages, they will be left at the mercy of their white majority state neighbors, indeed Federal enforcement may assist the white supremacists. They have something to prove, and so I think we can trust that at the hands of black police, black juries and black judges, whites who have a decent reasonable doubt defense will get due protection; in cases where racial conflict is not at issue, these will be fair, as fair as any due process can be.
The difference between OTL and the redrawn state boundaries situation is then that OTL, the white-majority state governments refused their proper duty in fairly and equally protecting the rights and interests of their African American citizens. With this remedied for African Americans, and those states properly and fairly also upholding the rights and interests of white citizens who remain there as well, white-majority state governments will stand out as of dubious legitimacy if they collectively foster terrorist acts across state lines.
You suggest it makes no difference if the Redeemer bases of support are across a state line, but it does. It even does legally and formally; if agents from one state are constantly crossing state lines to attack people in another state, this becomes a Federal matter! In the era Congress and Presidency are Republican controlled; if raiders from say West Florida are attacking people in Tombigbee, first of the the Tombigbee state government is within its rights to call out the militia, the National Guard in modern terms, and defend its state borders by intercepting and inspecting people who cross it. And if the state is deeply embroiled in an ongoing assault, the President and Congress have every right, indeed the duty, to investigate and take action. Tombigbee cannot on its own authority march on Pensacola and put a plainly criminal state governor of this white-majority state under arrest, but the President can authorize that same Tombigbee State Militia as an agency of the Federal forces, and instead or meanwhile to assist, order Marines from the Pensacola Naval Station to crack down. It won't come to that though because the politicians in the white majority capitals are generally not going to be stupid enough to put themselves into plainly liable positions, they are going to have to use plausible deniability, and that limits the options of Redeemer gangs on the borders.
Besides--if most blacks are living in a black majority state, and the few who remain in white majority states are free to leave and move to another state where they will definitely be safe and respected, what are the options of white supremacists, assuming they cannot simply conquer and rule the black-majority states wholesale? Are they motivated by revulsion against black people, or do they only want to force these black people to remain subservient to them? In the latter case, the remaining black population in the white states have some bargaining power! If the whites don't want them to leave, they need to start giving them some human consideration, some reason to stay. The ones who stay will have found their own reasons; attachment to the place one has grown up in, or even been settled in some years, is a strong human motive (often underestimated by bigots of various kinds) after all.
To be sure--if black folk are accused, tried and found guilty (never mind how honest these courts are!) of some felony, they can legitimately be compelled to work against their will and are not free to go.
But by and large, why should large numbers of whites support fanatical white supremacists of various kinds, if they now either reside in states with few black people to trouble them (or serve them) or as white minorities in a black state, enjoy the protection of living in a nation that is overall white-majority that would take serious issue with these scattered or enclaved whites being mistreated? Either way whites have little to fear. They are frustrated by being unable to subjugate their former slave class again for profit and glory, but that then is really the question--does adopting this scheme of states reorganized effectively check the power of Southern white majorities to subjugate the black people? I think it clearly does.
So--subjugation without a strong and plain just cause is not an option; claiming a just cause on the grounds of black outrages against whites is far fetched when whites have such overwhelming power over the handful of black folk in their majority states, while in the black majority states the black majorities know darn well they cannot allow unjust discrimination against their white minorities.
Over time then, the antebellum caste system in which slaves were deeply integrated into the private lives of powerful white people and communities were demographically mixed will give way to a far less mixed system in which blacks and whites might rarely see each other at all. I don't think that this is optimal, but I do think it gives the African American state residents a fair shot at competing on nearly equal terms that over time become more and more plainly equal. Over time, white supremacy as an ideology and passion will weaken and wither, and voluntary and mutually agreeable mixing of white and black populations will become more common.
I suspect that if separate reorganized states are feasible to create and can overcome the problems you note, it probably would also be possible to use the prewar state boundaries too and structure shared power within states so as to secure the freed people population. In other words, I don't suppose just creating a racial "Grand Apartheid" solution (not that that is a just name really--Apartheid by definition had a highly unjust thumb on the scales to appropriate the majority of resources for a highly privileged minority and use the reciprocal overcrowding and deprivation of the majority to strong-arm them into useful subservience without accountability of any kind; the partition of the South between black and white would be much fairer and I do think the African Americans could do very well with the six state territories the map offered suggests) is a silver bullet that will absolutely guarantee success (it had better though, considering how drastic a solution it is!) nor would I think it would be absolutely necessary to do this either.
However I do think that if it had been done, successful Reconstruction would be more feasible.
As I originally said I think it is unfortunate to rely on separation of "races"-but of course it would not be absolute.
If the Union waits until the South has surrendered wholesale, then your point about whole states voting with essentially all of their antebellum white electorate, and each one committed to retaining old state boundaries (and not incidentally, their ability to extract the benefits of African American labor at low cost and with no accountability to these populations with them!) is strong.
This is why I suggest it is best done during the war, taking the Virginia case as a useful first example.
Note that these shenanigans are possible only in states in secession. The states of Maryland, Delaware, Kentucky and Missouri have a Sword of Damocles placed not over their heads but pretty head-adjacent! As long as they play nice and do not secede and participate in the Union efforts, their territorial integrity is completely guaranteed. This would help offset the tendency of Lincoln telegraphing early in the Civil War that indeed the ultimate fate of all African American is to be freed/