His story has come WAY to far for him to simply be beheaded by Stannis in front of the old gods. That might end up happening in the end, but not before said redemption takes place. (His knowledge of Winterfell/Bolton troops/Bran and Rickon is of a lot of use)
It really depends upon which GRRM writes the next book. if it is the GRRM that wrote the first three books Theon should be dead soon, but I have my doubts. The best way I can think of describing it is the distinction between using a headsman and the Old Way. Ned said that killing should be hard and that a lord had an obligation to hear the last words and swing the sword himself, and if you couldn't then maybe that person doesn't deserve to die
GRRM has heard their words (technically he wrote them) and has had trouble killing off players in the game of thrones in the two latest novels. It seems he has become too attached to people do what is necessary for the story to continue, and I fear someone else is going to have to force GRRM to do what is needed to properly finish the story.