Let P, Q, R, S be the midpoints of AB, BC, CD, DA. Experiments (below) show that PQRS is a parallelogram for non-convex and for self-intersecting ABCD as well.

(i) The reasoning in the text uses only the Midpoint Theorem in the four triangles ABC, ADC, BCD and BAD. These are genuine triangles whenever no three of A, B, C, D are collinear, whether ABCD is convex, non-convex or self-intersecting.
-
In △ABC: PQ∥AC and PQ=2AC — Midpoint Theorem. In fact going from P to Q is half of going from A to C.
-
In △ADC: SR∥AC and SR=2AC — Midpoint Theorem; going from S to R is also half of going from A to C.
-
So PQ and SR are equal, parallel and point the same way, and PQRS is a parallelogram (Theorem 5). (Steps with △BCD and △BAD give QR∥PS∥BD and QR=PS=2BD in the same way.)
Nothing in this argument uses convexity, so the theorem holds for all three kinds of quadrilaterals. Its sides are always parallel to the two diagonals AC and BD and half as long.
(ii) The sides of PQRS are parallel to AC and to BD. If AC and BD point in different directions, PQRS has two genuinely different side directions and is a true parallelogram. It collapses to a single segment exactly when AC is parallel to BD: then all four sides lie along one line through P, Q, R, S.
This can happen only for a self-intersecting ABCD. In a convex quadrilateral the diagonals AC and BD cross; in a non-convex one, one vertex lies inside the triangle of the other three, so the line through it and the opposite vertex meets the other diagonal; in both cases AC and BD cannot be parallel. Example: A(0,0), B(0.6,2.4), C(4,0), D(3.2,2.4) give AC∥BD (both horizontal), and the midpoints P(0.3,1.2), Q(2.3,1.2), R(3.6,1.2), S(1.6,1.2) all lie on the line y=1.2.
(iii) Yes. Even if A, B, C, D are not in one plane, each of the triangles ABC, ADC, BCD, BAD lies in its own plane, so the Midpoint Theorem applies in each one. We get PQ∥AC∥SR with PQ=SR=2AC. Two lines parallel to the same line are parallel to each other (this is true in space too), so the parallel segments PQ and SR lie in one plane, and PQRS is a parallelogram lying in that plane.
So the Varignon parallelogram of a non-planar quadrilateral is still a flat parallelogram, even though ABCD itself is not flat. (Also, for a non-planar ABCD the lines AC and BD can never be parallel, since two parallel lines lie in one plane; so the exception in (ii) cannot occur.)