Apologies for what will probably be a comment-answer hybrid (and a comment probably too long to fit in the comment box).
One thing you say in your question is that you want an approximate solution vector. Have you considered iterative methods? There, the approximate inverse of $M$ could be used as a preconditioner in concert with some iterative method (GMRES, BiCGStab, etc.) to maintain approximate solution vectors, and the approximate solution for one linear system could then be used as an initial guess for the solution of a perturbed linear system.
To update the preconditioner in response to single-element (or low-rank) perturbations, you could use Sherman-Morrison(-Woodbury). Depending on the perturbation, the approximate inverse may still be an effective preconditioner even without updating.
I don't know how fast approximate matrix multiplication might degrade the solution of an iterative linear system; I would guess that it would be more forgiving in forming the preconditioner, since that can be approximate. After forming the preconditioner, I would stick to standard matrix-vector products for the solver iterations (for GMRES iterations, or whatever iterative method you consider using).
Of course, this entire discussion might be moot, depending on the size of $M$. If it's sufficiently small, it might be worth just solving every time; I assume it's relatively large, or we wouldn't be having this discussion.