determine cube orientation given one side in a perspective projection

Yes, it is always possible, and no, the solution is not unique. There is a simple construction that will give the locus of solutions.

The quadrilateral $T$ will determine two vanishing points, $L$ and $R$. The key is then to look for the vertical axis point, $\textit{VAP}$, from which all angles to the line through $LR$ are true angles. (This is analogous to the station point in one-point perspective.) Observe that $\textit{VAP}$ will lie on the circle with diameter $LR$, for the angle subtended by $LR$ from $\textit{VAP}$ must be a right angle.

Next observe that since $T$ is square, the same applies to the diagonals. In other words, extending the diagonals to the horizon through $LR$ gives two additional vanishing points, and $\textit{VAP}$ must be on the circle having those points as diameter.

It follows that $\textit{VAP}$ is on the intersection of these two circles. Now drop a perpendicular from $LR$ through $\textit{VAP}$ and choose a third vanishing point $V$ on that line; this is the locus of solutions. ($V$ should of course be far enough away such that $LVR$ is an acute triangle, which is to say that it should be on the far side of $\textit{VAP}$.) You may then proceed to construct the remainder of the cube.