If $A^2 + A = 0$, then the minimal polynomial of $A$ divides $t^2+t = t(t+1)$. That means that the characteristic polynomial of $A$ must be of the form $(-1)^nt^k(t+1)^r$, where $k+r=n$. $\lambda=0$ cannot be a root, though (since you specify that $A$ is invertible, so $0$ is not an eigenvalue), so the characteristic polynomial is necessarily $(-1)^n(t+1)^n$.
But that means that the minimal polynomial of $A$ must be $t+1$ (since it must divide the characteristic polynomial, and also $t(t+1)$). This implies that $A+I=0$, hence $A=-I$.
Added. If we drop the requirement that $A$ be invertible, then the invertible case proceeds as above. In the noninvertible case, the minimal polynomial is $t(t+1)$ or $t$. If it is $t$, then $A=0$. If the minimal polynomial is $t(t+1)$, then the matrix is diagonalizable (since the minimal polynomial splits and is square free), and the only eigenvalues are $0$ and $-1$. So the matrix $A$ is similar to a diagonal matrix in which every diagonal entry is $0$ or $-1$.
In summary, if we drop the requirement that $A$ be invertible, then there are $n+1$ similarity classes for possible $A$'s, each similarity class corresponding to a diagonal matrix that has $k$ diagonal entries equal to $0$, followed by $n-k$ entries equal to $-1$s in the diagonal, $k=0,\ldots,n$.