From the 2-D space there will be 2 valid rectangles that can be built. Without knowing the original matrix projection, you won't know which one is correct. It's the same as the "box" problem: you see two squares, one inside the other, with the 4 inside vertices connected to the 4 respective outside vertices. Are you looking at a box from the top-down or the bottom-up?
That being said, you are looking for a matrix transform T where...
{{x1, y1, z1}, {x2, y2, z2}, {x3, y3, z3}, {x4, y4, z4}} x T = {{x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}}
(4 x 3) x T = (4 x 2)
So T must be a (3 x 2) matrix. So we've got 6 unknowns.
Now build a system of constraints on T and solve with Simplex. To build the constraints, you know that a line passing through the first two points must be parallel to the line passing to the second two points. You know a line passing through points 1 and 3 must be parallel to the lines passing through points 2 and 4. You know a line passing through 1 and 2 must be orthogonal to a line passing through points 2 and 3. You know that the length of the line from 1 and 2 must equal the length of the line from 3 and 4. You know that the length of the line from 1 and 3 must equal the length of the line from 2 and 4.
To make this even easier, you know about the rectangle, so you know the length of all the sides.
That should give you plenty of constraints to solve this problem.
Of course, to get back, you can find T-inverse.
@Rob: Yes, there are an infinite number of projections, but not an infinite number of projects where the points must satisfy the requirements of a rectangle.
@nlucaroni: Yes, this is only solvable if you have four points in the projection. If the rectangle projects to just 2 points (i.e. the plane of the rectangle is orthogonal to the projection surface), then this cannot be solved.
Hmmm... I should go home and write this little gem. This sounds like fun.