How difficult is inverting a non-square matrix? Partially inspired by ring learning with errors (RLWE), I am trying to construct a cryptosystem that requires the use of a non-invertible matrix. 

Of the methods I've thought of to generate a matrix of determinant $0$, erasing a row/column or two seems the easiest, but I have no idea on how non-invertible this is. 

I would like to know about known methods of reconstructing an unknown square matrix with known structure from its product with a non-square matrix.
As far as I know, there is no well-behaved and canonical topology on finite fields that would enable a consistent and useful definition of pseudoinverse. The main point in computing pseudoinverses over the complex or real field is that they minimize some second moment error functional, since there is no unique inverse defined.

However, and I may regret this, but there is a recent 2015 conference paper from the Springer Lecture Notes in Electrical Engineering book series (LNEE, volume 339)[behind paywall] which claims to construct such a beast, subject to some strong conditions, but there is no proof of any error minimizing properties for such an inverse, and I'd be really surprised if it results in a meaningful definition of pseudoinverse for lattice based cryptosystems, though it might be worth looking into. A quick look at the paper titles show that this is a very generic and broad conference, not really focused on cryptography, but that may well not be important.