I was wondering if its possible to know if a matrix is invertible without row reducing it in attempt to make it I. If the matrix is not nxn, it is never invertible?
It doesn't make sense to speak of invertibility for non $\displaystyle n\times n$ matrices. In particular, a matrix $\displaystyle A$ which is $\displaystyle n\times m$ can be thought of a linear transformation $\displaystyle A:\mathbb{R}^m\to\mathbb{R}^n$ and so if $\displaystyle A$ is invertible, then the associated map is an isomorphism, which implies that $\displaystyle n=m$.
Well, since you liked the last explanation, perhaps one in the same vein. Pretend for a second that a matrix $\displaystyle A$ really is just a linear transformation $\displaystyle A:\mathbb{R}^n\to\mathbb{R}^n$, then one only has to check any of the following equivalent conditions:
1) $\displaystyle A$ is injective
2) $\displaystyle A$ is surjective
3) $\displaystyle A$ does not have zero as an eigenvalue
4) $\displaystyle \det(A)\ne0$
And there are many more, some of which are very similar to the ones I listed (e.g. 1) is easily seen to be eqiuvalent to the existence of a left inverse).
For $\displaystyle A\in\mathbb{K}^{m\times n}$ we have the concepts of left and right inverse: $\displaystyle B\in \mathbb{K}^{n\times m}$ is a left inverse of $\displaystyle A $ iff $\displaystyle BA = I_n$ and a left-invertible matrix is a matrix with at least one left inverse. Similar considerations for right inverse.