I rewatched the movie now, and I think you're right. There were a lot of details I'd forgotten.

The way I remember thinking about it was that he was jailed for revenge murder, then spent his life in jail doing his best to atone by being helpful (building a library, teaching, helping with taxes, etc.). When the prison system refuses to set him free despite him proving through his actions in prison that he's not a threat to society anymore (I hallucinated this part -- this happened to Red, not Andy), he escapes, and his freedom is his redemption.

I'm not a native English speaker, and I think I may have conflated redemption and atonement. Looking at some definitions, it looks like you can receive redemption without atonement -- it doesn't necessarily have to come from within.