When $A$ is nonsingular, the adjugate matrix $\operatorname{adj} A$ already works. However, if $A$ is singular, this approach fails because it is possible that $\operatorname{adj} A = 0$. Here's one alternate approach for this case.
Since the space of $n \times n$ matrices is finite dimensional, the infinite list of matrices $\{ I, A, A^2, \ldots \}$ is linearly dependent. Pick a linear dependence $ a_m A^{m} + a_{m-1} A^{m-1} + \cdots + a_{1} A^1 + a_0 I = 0 $ among the powers of $A$ such that $m$ is as small as possible, and define $B = a_m A^{m-1} + a_{m-1} A^{m-2} + \cdots + a_{1} I . \tag{$\dagger$}$
Now, first note that $-a_0 I = A B = B A$. Taking determinants on both sides, we have $(-1)^n a_0^n = 0$. So $a_0 = 0$, and hence $AB = AB = 0$. Finally, $(\dagger)$ says that $B$ is a linear combination of the first $m-1$ powers of $A$, and hence it is nonzero by our choice of $m$.