Yes but it would beyond blizzard skill.
Here is a senario i came up with that would grant them a chance at redemtion:
Act 1: Humilation:
Sylvanas compleetly crushes the horde rebels with superior tatic’s.
No blight, no nukes, just sheer badass generalship.
The horde rebel and there leaders have to flee.
They get sheltered in stormwind by andiun.
Protected by the gaurd.
While they are walking to the palace under heavy escort the people trow rotten fruit at them.
Thrall says: We deserve this.
And the entire horde looks ashamed.
Cut camera to an angry human woman planing to trow a rotten banana at baine.
Baine just looks away in shame.
The woman slowly lowers the banana with a look of pity on her face.
Meanwhile the rest just keep trowing rotten fruit.
Act 2: Reconciliation:
Over the course of two patch’s with several month between them we see the horde leaders and random npc act like normal people.
We have loth’mar playing chess with an old man, thrall is helping repair a damaged rooftop, baine is making orphans laugh, etc.
People will be slowly over time begin to see that they horde and alliance arent that different.
This is vital.
Right now all the common folk known about the horde is that they are bloodthirsty monsters.
Having them act as people, friends and family infront of other people will make them look more like them and less like unredeemable monsters.
Without this (for a lack of a beter word) humanization of the horde they will always be seen as monsters.
Blizzard must invoke pity on the good members of the horde.
While this is happening(and keep in mind this is just stuff you see, you dont get any quests)
The player’s and army of both alliance and horde(execpt sylvanas loyalist) are slowly pushing back sylvanas.
Sylvanas loyalist see the war from the losing side.
Act 3: Sacrifice:
One of sylvanas assasin is trying to murder Shandris Feathermoon while visiting stormwind for a briefing on how the war goes.
Attacking her in public in an attempt to sow fear among the population.
Saurfang or thrall trows himself between the assasin and save Shandris Feathermoon life.
They die shortly after we killed the assasin in full view of the entire city.
Act 4: Redemption:
Sylvanas and Nathanos are either captured or killed.
The horde is shattered and leaderless.
Jaina has died fighting on the frontlines.
Queen Talanji claims rulership over the horde and offers the rebels a second chance to join them against the hated alliance.
The rebel leaders give a grand speech on how they constantly fight the alliance and all it did was cause suffering to both side’s and that this cycle of hatred has to end.
This speech is so moving(and i cant writte speeches so someone else has too) that queen Talanji agree’s to let bygones be bybones.
Both she and andiun agree to allow there people to mingle but remain independed.
Too much bad blood that needs time to heal.
Now the slow road to healing has begun.
Time for the next expension.
They key to redemption lies in showing us (not telling us but showing us) that not all horde members are bloodthirsty murderers but people.
And that the horde accepts that the constant war is just pointless destruction.
By having the race’s mingle(aka cross faction gameplay) the alliance and horde leadership encourge’s people to let go of there hate and work togather.
This also justify’s all future pvp as people who just cant let go of there haterd.
Tyranda is going to need elune to stop her from murdering the horde as:
ONLY THE GODDESS CAN FORBID ME ANYTHING!!!
Nothing short of elune telling her to stop will be believeable.
If all goes according to plan.
The horde that remains has learned that pointless war is stupid, those who want war are either dead or the minority, and the alliance has been shown to accauly can win a war without needing the horde infighting to do it.
The thing that is needed for the horde to be redeemed is that people on both factions can see that there are those in the horde who feel ashamed of what there faction has done.
For without that shame, that regret.
They will always just be monsters.