Inverse of non-square matrix

Yes, it's true (assuming that $n$ and $m$ are finite for this answer). Here's an argument:

1. to have a right inverse is to have independent columns.
2. to have a left inverse is to have indep. rows.
3. the number of indep. cols is the number of indep. rows.

Details:

The first column of $AX$ can be thought of as a linear combination of the cols of $A$ by the entries of the first col of $X$; the same goes for each other col. The fact that $AX = I$ then means that the span of the columns of $I$ is included in the span of the columns of $A$, hence, if $A$ is $n \times k$, we know that the cols of $A$ span $\mathbb R^k$; there are $k$ indep. cols.

The same argument applies to rows.

For part 3, one cheap argument relies on determinants: $p$ (column) $n$-vectors are independent if and only if you can select $p$ of the $n$ rows to form a $p \times p$ matrix whose determinant is nonzero. Thus you cannot have more than $n$ independent $n$-vectors. The same applies to row-vectors.

Finally, if the matrix is non-square, the number of independent rows or columns is at most the smaller of the number of rows and number of cols, hence one set or the other is not independent, so either a left or right inverse can't exist.

Another argument: let $K$ be the base field. $A$ is the matrix of a linear map $u$ from $K^n$ to $K^m$. A right inverse $B$ is the matrix of a linear map $v\colon K^m\rightarrow K^n$ such that $uv=\operatorname{id}_{K^m}$, which implies $u$ is surjective.

Similarly, the existence of a left inverse implies $u$ is injective. So if $A$ has both a right and a left inverse, $u$ is an isomorphism, $m=n$ and $A$ is a square matrix.