I'm going to write an answer using vectors.
Let $O$ be the intersection point of $AC, BD$.
Let $$\vec{OA}=\vec{a}, \vec{OB}=\vec{b}, \vec{OC}=k\vec{a}, \vec{OD}=l\vec{b}$$
where $k,l\lt 0.$
Letting $E,F,G,H$ be the midpoints of $AB, BC, CD, DA$ respectively, we have
$$\vec{OE}=\frac{1}{2}\vec a+\frac 12\vec b,\vec{OF}=\frac 12\vec b+\frac k2\vec a, \vec{OG}=\frac k2\vec a+\frac l2\vec b, \vec{OH}=\frac 12\vec a+\frac l2\vec b.$$
Letting $I$ be the intersection point of $EG, FH$, there exist $m,n$ such that
$$\vec{EI}=m\vec{EG}, \vec{FI}=n\vec{FH}.$$
The former gives us
$$\vec{OI}-\vec{OE}=m\left(\vec{OG}-\vec{OE}\right)\iff \vec{OI}=(1-m)\vec{OE}+m\vec{OG}=\frac{1-m+mk}{2}\vec a+\frac{1-m+ml}{2}\vec b.$$
The latter gives us
$$\vec{OI}-\vec{OF}=n\left(\vec{OH}-\vec{OF}\right)\iff \vec{OI}=(1-n)\vec{OF}+n\vec{OH}=\frac{k-kn+n}{2}\vec a+\frac{1-n+nl}{2}\vec b.$$
Now since $\vec a$ and $\vec b$ are linearly independent, the following has to be satisfied :
$$\frac{1-m+mk}{2}=\frac{k-kn+n}{2}\ \text{and} \frac{1-m+ml}{2}=\frac{1-n+nl}{2}.$$
These give us $m=n=1/2$ since $(k,l)\not=(-1,-1).$
Hence, we get
$$\vec{OI}=\frac{k+1}{4}\vec a+\frac{l+1}{4}\vec b.$$
On the other hand, letting $P,Q$ be the midpoints of $AC, BD$, we have
$$\vec{OP}=\frac{k+1}{2}\vec a, \vec{OQ}=\frac{l+1}{2}\vec b.$$
Finally, we obtain
$$\vec{PI}=\frac 12\vec{PQ}.$$
Since this represents that $I$ is on the line $PQ$, we now know that we get what we want. Q.E.D.
P.S. If $(k,l)=(-1,-1)$, then $ABCD$ is a parallelogram, which is an easy case.
(Someone draw a picture of this because I don't know how)
To answer your second question, yes, a segment between two midpoints is parallel to the triangle's opposite side. In this case, call the intersection between $\overline{BH}$ and $\overline{MN}$ $P$, and draw altitude $\overline{MH'}$ perpendicular to $\overline{AC}$. Notice that $\overline{MH'} || \overline{BH}$, so $\angle AMH' = \angle ABH$, and therefore, $\angle BAC = \angle BMN$, so $\overline{MN} || \overline{AC}$.
Additionally, in this case $\overline{MN}$ bisects $\overline{BH}$. This is because $\triangle AMH' \cong \triangle MBP$ via Angle-Side-Angle, so $MH' = BP$. We also have $MH' = PH$, so $\overline{MN}$ does indeed bisect $\overline{BH}$, and it forms right angles because $\overline{MN} || \overline{AC}$.
Best Answer
A good diagram surely helps. First draw $\ell_1$ cutting sides $AB,BC,CA$ of $\triangle ABC$ in $X,Y,Z$ respectively. Now take points $X',Y'$ on $AB,BC$ respectively so that $XM_C=X'M_C$ and $YM_A=Y'M_A$. Then the condition that $\ell_1,\ell_2$ meet the sides symmetrically across midpoints mean, $\ell_2$ pass through $X',Y'$.
It should be considered an exercise, preliminary to current question, to show that intersection of $\ell_2$ with $AC$, $Z'$, lies symmetrically to $Z$, that is, $ZM_B=Z'M_B$.
For such a configuration, the angle between $\ell_1,\ell_2$ could vary; here it is given that $\angle(\ell_1,\ell_2)=90^\circ$. For this constraint, one has to show that their intersection point $P$ lies on the circle through the three midpoints.
It is clear that $\angle M_AM_CM_B = \angle C$. For right $\triangle ZPZ'$, $M_B$ is circumcenter and $PM_B=Z'M_B$. So $\angle M_BPZ'= \angle M_BZ'P$. Similarly $PM_AY'$ is isosceles and $\angle M_APY' = \angle M_AY'P=\angle CY'Z'$.
In $\triangle Y'CZ'$, we see the exterior angle $$\angle C = \angle CY'Z' + \angle CZ'Y' =\angle M_APY' + \angle M_BPZ' = \angle M_APM_B $$
Thus $\angle M_APM_B = \angle M_AM_CM_B$ and it follows that $P$ lies on the said circle.