There is a rectangle in 3-dimensional space. If I am only given the $x$ and $y$ coordinates, how do I find the $z$ coordinates? We are given the $x$ and $y$ coordinates of the four vertices of a rectangle.
How do I find the $z$-coordinates?
I know that this 3 dimensional rectangle must obey all the usual conditions of rectangle.
Opposite sides are equal.
The angles between two adjacent sides are 90 degrees.

(Rewritten after missing an entire degree of freedom!)
Let's say the vertices are in (clockwise or counterclockwise order) $\vec{A} = (x_A, y_A, z_A)$, $\vec{B} = (x_B, y_B, z_B)$, $\vec{C} = (x_C, y_C, z_C)$, and $\vec{D} = (x_D, y_D, z_D)$.
In order for the quadrilateral to be a parallelogram, pairs of opposing sides must be equal:
$$\left\lbrace\begin{aligned}
\vec{B} - \vec{A} &= \vec{C} - \vec{D} \\
\vec{D} - \vec{A} &= \vec{C} - \vec{B} \\
\end{aligned}\right. \quad \iff \left\lbrace\begin{aligned}
x_A - x_B + x_C - x_D &= 0 \\
y_A - y_B + y_C - y_D &= 0 \\
z_A - z_B + z_C - z_D &= 0 \\
\end{aligned}\right. \tag{1}\label{G1}$$
which means we can ignore $\vec{C}$ completely, because it is defined exactly by the three other points (via $\vec{C} = \vec{B} + \vec{D} - \vec{A}$), if it is a parallelogram.  (And rectangles and squares are always also parallelograms.)
First, check if the coordinates are valid for any rectangle that is perpendicular to the $z$ axis. If
$$(x_D - x_A)(x_B - x_A) + (y_D - y_A)(y_B - y_A) = 0 \tag{2a}\label{G2a}$$
then all real $z_A = z_B = z_C = z_D$ are valid solutions, as are $z_A = z_B \ne z_C = z_D$ and $z_A = z_D \ne z_B = z_C$.  (The latter are solutions because changing $z_A \to z_A + h$ and $z_B \to z_B + h$, or $z_A \to z_A + h$ and $z_D \to z_D + h$ is still a rectangle, increasing $h$ in magnitude just makes the rectangle taller or wider.)
For nontrivial solutions, we need all four angles of the parallelogram to be right angles:
$$\left\lbrace\begin{aligned}
\bigl( \vec{D} - \vec{A} \bigr) \cdot \bigl( \vec{B} - \vec{A} \bigr) &= 0 \\
\bigl( \vec{A} - \vec{B} \bigr) \cdot \bigl( \vec{C} - \vec{B} \bigr) &= 0 \\
\bigl( \vec{B} - \vec{C} \bigr) \cdot \bigl( \vec{D} - \vec{C} \bigr) &= 0 \\
\bigl( \vec{C} - \vec{D} \bigr) \cdot \bigl( \vec{A} - \vec{D} \bigr) &= 0 \\
\end{aligned}\right.$$
Because $\vec{C} = \vec{D} + \vec{B} - \vec{A}$, these all simplify to the same rule,
$$(x_B - x_A)(x_D - x_A) + (y_B - y_A)(y_D - y_A) + (z_B - z_A)(z_D - z_A) = 0$$
i.e.
$$(z_B - z_A)(z_D - z_A) = - (x_B - x_A)(x_D - x_A) - (y_B - y_A)(y_D - y_A)$$
which we can solve for $z_D$ (noting that we have already covered the $z_A = z_B$ cases in $\eqref{G2a}$):
$$z_D = z_A - \frac{ (x_B - x_A)(x_D - x_A) + (y_B - y_A)(y_D - y_A) }{z_B - z_A}, \quad z_A \ne z_B \tag{2b}\label{G2b}$$
meaning we can choose any pair of reals $z_A \ne z_B$, and $\eqref{G2b}$ and
$$z_C = z_D + z_B - z_A$$
will yield a valid rectangle.

Let's test this with
$$\vec{A} = \left[\begin{matrix} 3 \\ 3 \\ z_A \end{matrix}\right], \quad
\vec{B} = \left[\begin{matrix} 10 \\ 5 \\ z_B \end{matrix}\right], \quad
\vec{C} = \left[\begin{matrix} 11 \\ 8 \\ z_B + z_D - z_A \end{matrix}\right], \quad
\vec{D} = \left[\begin{matrix} 4 \\ 6 \\ z_D \end{matrix}\right]$$
(which yields $13 \ne 0$ for $\eqref{G2a}$, so $z_A=z_B=z_C=z_D$ are not valid rectangles).
Rule $\eqref{G2b}$ simplifies to
$$(z_D - z_A)(z_B - z_A) = -13 \quad \iff \quad z_D = z_A - \frac{13}{z_B - z_A}, z_A \ne z_B$$
Here are some randomly generated solutions:
$$\begin{array}{cc|cccc}
z_A & z_B & \vec{A} & \vec{B} & \vec{C} & \vec{D} \\
\hline
0 & 1 & (3, 3, 0) & (10, 5, 1) & (11, 8, -12) & (4, 6, -13) \\
1 & 0 & (3, 3, 1) & (10, 5, 0) & (11, 8, 13) & (4, 6, 14) \\
1 & -1 & (3, 3, 1) & (10, 5, -1) & (11, 8, 5.5) & (4, 6, 7.5) \\
-3 & 10 & (3, 3, -3) & (10, 5, 10) & (11, 8, 9) & (4, 6, -4) \\
\end{array}$$
