The following is a proof of constructibility, with some standard details missing, mostly the fact that the arithmetical operations and square root can be carried out by straightedge and compass.
In principle, one can use the proof to give instructions on how to carry out the construction. However, the construction one gets has little real geometric content. There is undoubtedly an elegant geometric construction. But the algebraic approach used below has the nice feature of being essentially automatic. If one has a certain amount of background, a glance at the problem shows that an inscribed rhombus is constructible.
We are given a convex quadrilateral $ABCD$, with the vertices going say counterclockwise. Let $P$, $Q$, $R$, $S$ be points on the line segments $AB$, $BC$, $CD$, and $DA$.
Lemma: Suppose that $AP:BP=AS:DS$ and $CR:DR=CQ:BQ$. Then the lines $PS$ and $RQ$ are parallel.
Proof: They are both parallel to $BD$.
Corollary: If $AP:BP=AS:DS$ and $BP:BQ=DR:CR$ then $PQRS$ is a parallelogram.
In particular (not relevant here, but cute) if $P$, $Q$, $R$ and $S$ are bisectors of the sides they lie on, then one gets the unexpected result that $PQRS$ is a parallelogram.
A little play will show that if we choose $P,Q,R,S$ as in the corollary, but with $AP$ small, then $PS$ will be smaller than $PQ$. And if we choose $P$ so that $BP$ is small, then $PS$ will be larger that $PQ$. So a choice somewhere in between is just right, we get $PS=PQ$, and therefore a rhombus.
Now we leave classical geometry. Choose a coordinate system with $A$ at the origin, and with $B$ say at $(1,0)$. (It doesn't matter.) Points $C$ and $D$ then have "known" coordinates, and all the lines of our quadrilateral have known linear equations, with coefficients constructible from our given points.
Let $P=(t,0)$. Find the equation of the line through $(t,0)$ that is parallel to $BD$. We can now find the coordinates of the point $S=(s_1(t),s_2(t))$ where this line meets $AD$. The coordinates of $S$ are linear in $t$.
Find also the equation of the line through $(t,0)$ that is parallel to $AC$. We can now find the coordinates of the point $Q=(q_1(t),q_2(t))$ where this line meets $BC$. The coordinates of $Q$ are linear in $t$.
The condition $PS=PQ$ then becomes
This is a quadratic equation, with coefficients that are constructed using addition, subtraction, multiplication, and division from coordinates of our given points.
The ordinary arithmetical operations can be done by straightedge and compass, as can square root. So the geometrically relevant solution of Equation $(1)$ is constructible from our given points. Now that we have $P$, the rest of the construction is done by drawing parallels.