Suppose that A is an $n\times m$ matrix with $ n\neq m$.
Here's my reasoning.
Every nonpivot column corresponds to a free variable in the system Ax = 0. Each free variable becomes a parameter, and each parameter is multiplied times a basis vector of null(A). Therefore the number of nonpivot columns equals nullity(A). Since rank(A) + nullity(A) = m, the nullity(A) must be greater than zero.
I'm not sure if I'm justified in stating the last sentence. Any suggestions or can you provide a different proof?