You can check the rank of $\left[ \begin{array}{c|c}A &b \end{array} \right]$ if that is an alternative way that you are looking for (note that row reduced echelon form is also a way of to compute the rank).
In particular, if $A$ is fat i.e. number of rows $m$ is less than the number of columns $n$, then infinitely many solution exists. If $m=n$ then either the matrix is invertible and every $b$ has a solution in the form of $x=A^{-1}b$ or $A$ is singular and you can reduce it to either a fat or tall matrix with full row/column rank.
The last option is the tall matrix case. Then you can simply check if $\operatorname{rank}\left[ \begin{array}{c|c}A &b \end{array} \right]>\operatorname{rank}A$ In case of a positive answer : No $x$ can lead to that particular $b$ (which is usually the case). Hence the popularity of least squares solution.