I found the answer in this book (in Section $6.4.14$, “Determinants, Ranks and Linear Equations”). I'd tried using a similar Laplace expansion myself but was missing the idea of using the largest dimension at which the minors are not all annihilated by the same non-zero element. I'll try to summarize the argument in somewhat less formal terms, omitting the tangential material included in the book.
Let $A$ be an $m\times n$ matrix over a commutative ring $R$. We want to find a condition for the system of equations $Ax=0$ with $x\in R^n$ to have a non-trivial solution. If $R$ is a field, various definitions of the rank of $A$ coincide, including the column rank (the dimension of the column space), the row rank (the dimension of the row space) and the determinantal rank (the dimension of the lowest non-zero minor). This is not the case for a general commutative ring. It turns out that for our present purposes a useful generalization of rank is the largest integer $k$ such that there is no non-zero element of $R$ that annihilates all minors of dimension $k$, with $k=0$ if there is no such integer.
We want to show that $Ax=0$ has a non-trivial solution if and only if $k\lt n$.
If $k=0$, there is a non-zero element $r\in R$ which annihilates all matrix elements (the minors of dimension $1$), so there is a non-trivial solution
$$A\pmatrix{r\\\vdots\\r}=0\;.$$
Now assume $0\lt k\lt n$. If $m\lt n$, we can add rows of zeros to $A$ without changing $k$ or the solution set, so we can assume $k\lt n\le m$. There is some non-zero element $r\in R$ that annihilates all minors of dimension $k+1$, and there is a minor of dimension $k$ that isn't annihilated by $r$. Without loss of generality, assume that this is the minor of the first $k$ rows and columns. Now consider the matrix formed of the first $k+1$ rows and columns of $A$, and form a solution $x$ from the $(k+1)$-th column of its adjugate by multiplying it by $r$ and padding it with zeros. By construction, the first $k$ entries of $Ax$ are determinants of a matrix with two equal rows, and thus vanish; the remaining entries are each $r$ times a minor of dimension $k+1$, and thus also vanish. But the $(k+1)$-th entry of this solution is non-zero, being $r$ times the minor of the first $k$ rows and columns, which isn't annihilated by $r$. Thus we have constructed a non-trivial solution.
In summary, if $k\lt n$, there is a non-trivial solution to $Ax=0$.
Now assume conversely that there is such a solution $x$. If $n\gt m$, there are no minors of dimension $n$, so $k\lt n$. Thus we can assume $n\le m$. The minors of dimension $n$ are the determinants of matrices $B$ formed by choosing any $n$ rows of $A$. Since each row of $A$ times $x$ is $0$, we have $Bx=0$, and then multiplying by the adjugate of $B$ yields $\det B x=0$. Since there is at least one non-zero entry in the non-trivial solution $x$, there is at least one non-zero element of $R$ that annihilates all minors of size $n$, and thus $k\lt n$.
Specializing to the case $m=n$ of square matrices, we can conclude:
A system of linear equations $Ax=0$ with a square $n\times n$ matrix
$A$ over a commutative ring $R$ has a non-trivial solution if and only
if its determinant (its only minor of dimension $n$) is annihilated by
some non-zero element of $R$, that is, if its determinant is a zero divisor or zero.
I would not call the following argument elementary, but maybe fundamental:
The matrix $A$ defines an endomorphism $f$ of the $R$-module $R^n$.
When $f$ is left-invertible or invertible, it has zero kernel.
Hence in proving the equivalence left-invertible $\Leftrightarrow$ invertible
we can assume that we have an exact sequence
$0 \rightarrow R^n \stackrel{f}{\rightarrow} R^n \rightarrow C \rightarrow 0$
where $C$ is the cokernel of $f$.
But then $f$ is left-invertible if and only if the above exact sequence splits. Hence $f$ is left-invertible if and only if $R^n \cong R^n \oplus C$.
But this latter condition is true only when $C=0$.
Hence $f$ is left-invertible if and only if it is an isomorphism.
Remark: There are quite a bit "non-elementary arguments" in actually establishing that $C=0$: tensor the equality $R^n \cong R^n \oplus C$
with $\kappa(m)=R_m/mR_m$, where $m$ is some maximal ideal, to obtain $\kappa(m)^n \cong \kappa(m)^n \oplus C_m/mC_m$. This is an isomorphism of finite dimensional $\kappa(m)$-vector spaces. Since the dimensions of left and right sides must be equal, we see that $C_m/mC_m$ must be zero. Then Nakayama's Lemma implies that $C_m=0$. But an $R$-module whose localization at every maximal ideal is zero must be the zero module.
Conclusion: If you are willing to take your scalars to be a ring instead of a field, then in general you need to resort to more sophisticated arguments. But in this particular case we have that the beautiful equation
$adj(A) A = det(A) I$ still holds and we could have avoided the above commutative-algebraic arguments. I will leave it you to decide which one is more elementary :)
Best Answer
It seems like they (justly) don't define invertible matrices by the determinant, but instead by the relation $AB = BA = I$, which is the good notion of invertibility when looking at matrices as a ring.
That is, the condition with the determinant shouldn't be seen as a definition but as a theorem/proposition.