I think I have a solution (detailed below), but I would appreciate it if there were a nicer, simpler solution, particularly for Part I.
The general roadmap is as in the question. We'll use a convexity property of mutual information to reduce to the case in which the variable $i$ is independent of $x_1,x_2$. We can then solve this special case using the first strategy from the question.
Part I, reducing to $i$ independent of $x_1,x_2$.
Recall that the quantity $I(u:v)$ is a function of the probabilities $P[u=u_0]$ and $P[v=v_0|u=u_0]$ where $u_0,v_0$ range over the support of $u$ and $v$. When the kind of the form $P[u=u_0]$ are fixed, and the remainder are allowed to vary, it's known that $I(u:v)$ is convex. This is the key property that we'll exploit.
For each fixed assignment $x_1,x_2 \gets \hat{x}_1,\hat{x}_2$, we are given a distribution $\mu_{\hat{x}_1,\hat{x}_2}$ over $(i,y)$ with the property that $x_i = y$ always; the goal is to construct a new distribution $\nu_{\hat{x}_1,\hat{x}_2}$ over the choices of $(i,y)$ so that
we still have $x_i = y$ always
the distribution of $i$ under $\nu_{\hat{x}_1,\hat{x}_2}$ is independent of the choice of $x_1,x_2$
the mutual information satisfies
$$I_{\nu}(\; (i,y) \;:\; x_1,x_2 \;) \le I_{\mu}(\; (i,y) \;:\; x_1,x_2 \;)$$
where $\nu$ denotes sampling $x_0,x_1 \sim \mu$ and then sampling $(i,y)$ from $\nu_{\hat{x}_1,\hat{x}_2}$.
We'll do this by just defining $\nu_{\hat{x}_1,\hat{x}_2}$ to be the distribution that picks $\hat{x}_1',\hat{x}_2'$ uniformly at random, samples $i \sim \mu_{\hat{x}_1',\hat{x}_2'}$, and sets $y \gets \hat{x}_i$.
The distribution $\nu$ clearly has $x_i = y$ everywhere. Also, $i$ is clearly independent of $x_1,x_2$. So we just need to show the mutual information inequality.
To do this, suppose we fix a bijection $f_1$ from the support of $x_1$ to itself, and a bijection $f_2$ similarly wrt $x_2$. Let $\mu^{f_1,f_2}$ be the distribution over $x_1,x_2,i,y$ obtained by sampling $x_1,x_2 \sim \mu$, then sampling $i \sim \mu_{f_1(x_1),f_2(x_2)}$, and setting $y \gets x_i$. It follows that
For every $i_0$ in the support of $i$ and $y_0$ in the support of $y$, we have
$$\begin{align*}
\mathrm{Pr}_{\mu^{f_1,f_2}}[ i=i_0, y=y_0 ]
&= \mathbb{E}_{x_1,x_2\sim\mu}\left[
\mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[i=i_0,y=y_0]
\right] \\
&= \mathbb{E}_{x_1,x_2\sim\mu}\left[
\mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[i=i_0] \cdot
\mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[y=y_0 \mid i=i_0]
\right] \\
&= \mathbb{E}_{x_1,x_2\sim\mu}\left[
\mathrm{Pr}_{\mu\mid_{f_1(x_1),f_2(x_2)}}[i=i_0]
\; ; \;
x_{i_0} = y_0
\right]
\end{align*}$$
and also
$$\begin{align*}
\mathrm{Pr}_{\mu}[ i=i_0, y=y_0 ]
&= \mathbb{E}_{x_1,x_2\sim\mu}\left[
\mathrm{Pr}_{\mu\mid_{x_1,x_2}}[i=i_0,y=y_0]
\right] \\
&= \mathbb{E}_{x_1,x_2\sim\mu}\left[
\mathrm{Pr}_{\mu\mid_{x_1,x_2}}[i=i_0] \cdot
\mathrm{Pr}_{\mu\mid_{x_1,x_2}}[y=y_0 \mid i=i_0]
\right] \\
&= \mathbb{E}_{x_1,x_2\sim\mu}\left[
\mathrm{Pr}_{\mu\mid_{x_1,x_2}}[i=i_0]
\; ; \;
x_{i_0} = y_0
\right]
\end{align*}$$
whence it follows that
$$\mathrm{Pr}_\mu\left[ i=i_0, y=y_0 \right]
=
\mathrm{Pr}_{\mu^{f_1,f_2}}\left[ i=i_0, y=f_{i_0}^{-1}(y_0) \right]
$$
and hence
$$H_{\mu^{f_1,f_2}}(\; i,y \;) = H_{\mu}(\; i,y \;)$$
and similarly for the conditional entropies
$$\begin{align*}
H_{\mu^{f_1,f_2}}(\; i,y \;\mid\; x_1,x_2 \;)
&= H_{\mu^{f_1,f_2}}(\; i \;\mid\; x_1,x_2 \;) \\
&= \mathbb{E}_{x_1,x_2\sim\mu} H_{\mu\mid_{f_1(x_1),f_2(x_2)}}( i,y ) \\
&= \mathbb{E}_{x_1,x_2\sim\mu} H_{\mu\mid_{x_1,x_2}}( i,y ) \\
&= H_{\mu}(\; i \;\mid\; x_1,x_2 \;) \\
&= H_{\mu}(\; i,y \;\mid\; x_1,x_2 \;)
\end{align*}$$
where the middle equality follows because the conditional entropy is an equally-weighted average over all the choices of $\hat{x}_1,\hat{x}_2$ in the support of $x_1,x_2$, and the effect of $f_1,f_2$ is just to shuffle the averaged quantities around.
Putting these two together, it follows that
$$I_{\mu}(\; i,y \;:\; x_1,x_2 \;) = I_{\mu^{f_1,f_2}}(\; i,y \;:\; x_1,x_2 \;)$$
Note that we can view sampling $i,y$ from $\nu_{\hat{x}_1,\hat{x}_2}$ as choosing $f_1,f_2$ uniformly and independently at random, and then sampling $i,y \sim \mu^{f_1,f_2}\mid_{\hat{x}_1,\hat{x}_2}$. So in that sense, the ensemble of conditioned distributions $\{\nu_{\hat{x}_1,\hat{x}_2}\}$ for $i$ is a convex combination, over choices of $f_1,f_2$, of the ensembles of conditioned distributions $\{\mu^{f_1,f_2}\mid_{\hat{x}_1,\hat{x}_2}\}$.
Hence, by the convexity property of mutual information, we can finally say that
$$I_\mu(\; i,y \;:\; x_1,x_2 \;) \ge I_\nu(\; i,y \;:\; x_1,x_2 \;)$$
Part II, assuming $i$ is independent of $x_1,x_2$, prove the claim.
This part is much easier. We can write
$$\begin{align*}
I(\; i,y \;:\; x_1,x_2 \;)
&= I(\; y \;:\; x_1,x_2 \;|\; i \;) + I(\; i \;:\; x_1,x_2 \;) \\
&= I(\; y \;:\; x_1,x_2 \;|\; i \;) \\
&= H( y | i ) - H( y | i,x_1,x_2 ) \\
&= H( y | i )
\end{align*}$$
Then, conditioning on $i=i_0$, we know $y = x_{i_0}$, and $x_{i_0}$ is independent of $i$, so $H(y | i=i_0) = H(x_{i_0}) = \log(m)$, and we're done.