None of the existing answers quite worked for me, so...
If $A$ has orthonormal columns, $A^T A=I$. $A^T A$ is full of dot products of pairs of columns of $A$. By orthogonality, these are all zero off of the diagonal. By orthonormality, these are all one on the diagonal.
If $A$ is rectangular, $A^T$ cannot be a true inverse of $A$. If $A$ is square with orthonormal (or even independent non-zero) columns, we have $A^{-1} A=I$, suggesting that $A^T$ could be $A^{-1}$. But how to rule out that there may be more than one $B$ such that $BA=I$?
Well, if $XY=Z$, every column of $Z$ is a linear combination of the columns of $X$, and every row of $Z$ is a linear combination of the rows of $Y$. But if $X$ has independent columns, there's precisely one unique linear combination of those columns that gives any particular vector result (including each column of $Z$), so $Y$ is uniquely determined by $X$ and $Z$. Similarly if $Y$ has independent rows, each row of $X$ is uniquely determined by $Y$ and $Z$.
The columns of $A$ are orthonormal so clearly independent. If (and only if) $A$ is square, its rows are independent. And by those uniqueness properties, if $A^T A=I$, we can conclude that $A^T=A^{-1}$.
Since $A^T=A^{-1}$, $A A^T=I$ also - the rows of $A$ are orthonormal because $A A^T$ is made of dot products of pairs of rows which are all one on the diagonal, zero elsewhere (as earlier with $A^T A$, but for rows not columns).
I'm still assuming $B A=I$ implies $A B=I$ with the same $B=A^{-1}$ both ways, so...
If $B$ is the left inverse of $A$, and $C$ is the left inverse of $B$, then $BA=I$ and $CB=I$ by definition. Multiplying both sides of $BA=I$ gives $CBA=C$, so $A=C$ -- the left inverse of the left inverse is the original matrix. We knew that anyway because the left inverse is the transpose (good job - otherwise I'd have to prove the existence of the left inverse of the left inverse). But substituting $A=C$, $BA=I$ becomes $BC=I$ and $CB=I$ becomes $AB=I$, so left inverses are right inverses too.
This answer still isn't a full self-contained proof because I haven't proved the uniqueness properties for linear combinations of independent vectors, or the properties of dot products, or that matrix multiplication is associative.