Finding the smallest eigenvalues of a large, but structured, matrix

Well, if you add $c I$ to your matrix, for some reasonable value of $c,$ it will become nonsingular. As for the left inverse, since your matrix is sparse, to compute the backward iteration you can use the conjugate gradient method, which will be very fast (there are fancier "Krylov space" methods, but you need not go there, unless conjugate gradient fails).

If it is a Laplacian then you not only know the smallest eigenvalue is zero, but you also know its corresponding eigenvector. You can use this information by essentially adding a single step to your procedure, it's something like adding back the mean of v to each element of Mv. Then use arnoldi to find the smallest (instead of second smallest) eigenpair.