In $M_n(\mathbb C)$, in general one needs to change at least $n$ coefficients to get an invertible matrix:
Take any $A \in M_n(\mathbb C)$, then $A - \frac{1}{p}I_n$ is invertible at a certain moment since $A$ has at most $n$ eigenvalues.
And with $0_n$, one needs to change $n$ coefficients.
Now, if we know that the rank of $A$ is $r$, I suppose $n-r$ changes have to be made to get an invertible matrix. Is there an elementary proof of this?
A single entry changes only a single column vector, hence the span of all new column vectors is at most the span of all other column vectors plus one additional dimension. Hence every single change can increase the rank by at most $1$.
At the same time, the above gives us a recipe: If the rank is $<n$, pick one column that is linearly dependent of the others, and change one entry that takes it out of the image space (this is guaranteed to be possible because not all of $e_1,\ldots, e_n$ are in the image space). This increases the rank by one. Repeat if necessary until you have full rank.