Sorry I'm being a bit terse, I'll try to explain what I'm doing more fully.
We start with a set of two by two matrices satisfying the algebra (I'm not going to require them to be hermitian, but you could). What we want to prove is that there is a similarity transformation S (again, not required to be unitary) such that [itex]S\alpha_i S^{-1}[/itex] are in the standard form of the Pauli matrices. The vital point is that the algebraic relations are unchanged under similarity transformations.
The way we do this is by slowly building up the Pauli matrices one at a time, and constructing S as a product.
At the first stage, we pick a similarity transform [itex]S_1[/itex] such that [itex]S_1\alpha_3 S_1^{-1}[/itex] is the diagonal Pauli matrix [itex]\sigma_3[/itex]. But there is nonuniqueness in this choice, in that we can pick [itex]S_2[/itex] such that [itex]S_2\sigma_3 S_2^{-1}=\sigma_3[/itex].
Now at the second stage, we want to put a second matrix into standard form. But any further similarity transformation we do must not disturb the matrix we have already constructed, so it must be of the form [itex]S_2[/itex] (commute with [itex]\sigma_3[/itex]). This is what I meant when I said 'residual transformation'.
Specifically, we find that [itex]S_2[/itex] must be diagonal. Since the overall scale of the similarity transformation is irrelevent, we can pick it to have the form [itex]\mathrm{diag}(\lambda,1)[/itex] for some nonzero [itex]\lambda[/itex]. The algebra, as you have said, constrains [itex]\alpha_1[/itex] to be of the form
[tex]
\begin{pmatrix}<br />
0 & a \\<br />
a^{-1} & 0<br />
\end{pmatrix}[/tex]
and by calculation applying similarity transformation [itex]S_2[/itex] to this just rescales [itex]a\to\lambda a[/itex]. So pick [itex]\lambda=a^{-1}[/itex] and you get the Pauli matrix [itex]\sigma_1[/itex].
Now the only similarity transformations that fix both the matrices we have constructed are proportional to the identity, so we have no freedom left. But the algebra constrains the third matrix to be [itex]\sigma_2[/itex] so we've proved what we set out to. The transformation [itex]S=S_2S_1[/itex].