The necessary and sufficient condition for existence of such random variable which forms the Markov chain $V\to X\to Z$ is "row linear independence" of the transition kernel from $X$ to $V$. Let $V\in\mathcal{V}$ and $X\in\mathcal{X}$ and also $|\mathcal{V}|=r$ and $|\mathcal{X}|=k$. Suppose $\mathcal{A}=\{P(\textbf{V}|x_i), ~ i=1,2,\dots, k\}$ is the set of all the rows of matrix $\{P(v|x)\}$. Consider the equation $P(\textbf{V})=\sum_{i=1}^k \alpha_i P(\textbf{V}|x_i)$ for $\alpha_i\geq 0$ and $\sum_i \alpha_i=1$ which has an obvious solution $\alpha_i=P(x_i)$ (which asserts that $P(\textbf{V})$  lies in the convex hull of $\mathcal{A}$). The condition "row linear independence" is needed to make sure this equation has other solutions as well. It is well-known that $\dim(\text{conv}(G))=\dim(\text{span}(G))-1$. Suppose  $\dim(\text{span}(G))=d$ and hence $\dim(\text{conv}(G))=d-1$. By assumption, $d\leq k-1$. By Caratheodory theorem, $P(\textbf{V})$ can be expressed as a convex combination of $d$ points in $\mathcal{A}$. Let $P(\textbf{V})=\sum_{i=1}^d \mu_iP(\textbf{V}|x_i)$. So, $[\mu_1, \mu_2, \dots, \mu_d, 0,0,\dots,0]$ is also another solution for $P(\textbf{V})=\sum_{i=1}^k \alpha_i P(\textbf{V}|x_i)$. It is easy to see that the solution set of this equation is a convex set because if $\psi$ and $\zeta$ are two solutions then $\lambda \psi + (1-\lambda)\zeta$ for $0\leq \lambda \leq 1$ is also a solution.
Therefore, each point in the solution set (like $P(\textbf{X})$) can be expressed as convex combination of $\mu$ and another point in the boundary of the set solution set, say $\nu$. 
Using all these said, we can construct a binary random variable $Z$ as the following:
$P(\textbf{X}|z_1)=\mu$, $P(\textbf{X}|z_2)=\nu$ and $\mu P(\textbf{X}|z_1)+ \nu P(\textbf{X}|z_2)=P(\textbf{X})$. 

Note that the $Z$ constructed above is independent with $V$ because it satisfies the equation $P(\textbf{V})=\sum_{i=1}^k \alpha_i P(\textbf{V}|x_i)$. Recall that for the above Markov chain the independence of $Z$ and $V$ implies $P(v)=\sum_{i=1}^k P(x_i|z) P(v|x_i)$ for all $v$ and $z$.