In general, if $n=1$, then you clearly can not choose $a$ as for example, if $R=k[x,x^{-1}]$ and $a=x$. So, already the choice of $a$ is not so arbitrary.
I am not sure what you mean by choosing the variables, but the proof of the Normalization does give you a `choice'. For simplicity, if you assume that $k$ is infinite and $R=k[x_1,\ldots, x_m]$ (some set of generators for $R$), if these are actually algebraically independent, you are done. Otherwise they satisfy an equation $f(x_1,\ldots, x_m)=0$ and then you can change the $x_i$'s linearly, so that $f$ is monic in $x_m$. This of course is slightly non-constructive. Then $R$ is integral over $S=k[x_1,\ldots, x_m]$ and you can continue.
May be you should look at the proof for projective varieties, where the successive choices are easier to make.