I'd go with Angel (Warren), Wolverine and Gambit as three of the horsemen as they were all horsemen in the comics. Wolverine would be war, Gambit would be Famine, Angel would be death. Wolverine would be captured, Gambit would go to Apocalypse for help controlling his powers and Angel would be brought in from the future after Apocalypse cut off his wings and brainwashed him into Death.
Now for Pestilence, let's assume that this is a character that has to do with disease as part of who he is. Let's also assume that some characters may need new origins and that without Stryker, Weapon X would presumably have Sublime, Sinister, Romulus and Sauron calling the shots but they may have some "failed experiments."
Now let's assume that Apocalypse would be able to fix one of these rejects and grant him his true potential.
I'm talking DEADPOOL!
Wolverine would get his metal claws back in the DOFP timeline but otherwise he'd be unchanged once cured. Gambit wouldn't undergo a radical physical transformation, he'd just have a bit more power so he'd be completely cured once he breaks Apocalypse's control. Archangel would be turned into this blue-skinned cybernetic monstrosity with wires coming out of his body and metal wings. Deadpool would have it worst to the point where he's ashamed to take off his mask anymore as well as being completely nuts. Granted, if Deadpool is made into a horseman, I'm already prepared for people expressing a ton of hate online for Bryan Singer.