Show $\lVert \mu - \nu \rVert \le \delta$ iff there are random variables $X,Y$ with distributions $\mu,\nu$ so that $P(X \neq Y) \le \delta$. 
Show that $\lVert \mu - \nu \rVert \le \delta$ if and only if there are random variables $X$ and $Y$ with distributions $\mu$ and $\nu$ so that $P(X \neq Y) \le \delta$.

FYI, this is Exercise 3.6.1 from the Durrett Probability (fifth edition) textbook. Also the textbook specifies $\lVert \mu - \nu \rVert \le 2\delta$, but I believe the $2\delta$ is a mistake and should be $\delta$.
\begin{align*}
    \lVert \mu - \nu \rVert \le \delta \iff P(X \neq Y) \le \delta
\end{align*}
We define total variation distance between two measures $\mu, \nu$ as follows, where $\mathcal{R}$ are the Borel sets on $\mathbb{R}$.
\begin{align*}
  \lVert \mu - \nu \rVert &=\sup_{A \in \mathcal{R}} \lvert \mu(A) - \nu(A) \rvert \\
\end{align*}
If $f,g$ are density functions corresponding to $\mu, \nu$, then, we have an equivalent and possibly more useful definition of total variation distance:
\begin{align*}
  \lVert \mu - \nu \rVert &= \int_\mathbb{R} \lvert f(x) - g(x) \rvert \, dx \\
\end{align*}
\begin{align*}
    P(X \neq Y) &= \int_\Omega 1_{X(\omega) \neq Y(\omega)} \, dP \\
\end{align*}
The standard way to define random variables that have given distributions, is first to get the CDF:
\begin{align*}
    F &: \mathbb{R} \to [0,1] \\
    F(x) &= \int_{-\infty}^x f(y) \, dy \\
    F(x) &= \mu((-\infty, x]) \\
\end{align*}
Define probability space $(\Omega, \mathcal{F}, P)$ with $\Omega = (0,1)$, $\mathcal{F} = \mathcal{R}$, $P$ be the Lebesgue measure. Then, our corresponding random variable with cumulative distribution function $F$ is:
\begin{align*}
    X &: \Omega \to \mathbb{R} \\
    X(\omega) &= \text{sup} \{ y : F(y) < \omega \} \\
\end{align*}
We can also make.a cdf $G$ corresponding to $\nu$ and $g$ and define a corresponding random variable $Y$.
From there, I'm stuck on what to try next.
 A: The $(\!\!\impliedby\!)$ direction is the easiest. To do this, take $\|\mu-\nu\|=\sup_A|\mu(A)-\nu(A)|$, and make the replacements
$$
\mu(A)=P(A\times \mathbb Z)=P(A\times A)+P(A\times A^c)\\
\nu(A)=P(\mathbb Z\times A)=P(A\times A)+P(A^c\times A)\\
$$
to conclude $\|\mu-\nu\|=\sup_A |\mu(A\times A^c)-\nu(A^c\times A)|$. How does $|\mu(A\times A^c)-\nu(A^c\times A)|$ relate to $P(X\neq Y)$?
For the $(\!\!\implies\!\!)$ direction, you need to construct random variables for which $P(X\neq Y)=\|\mu-\nu\|$. This part is quite hard; I cannot give hints for coming up with the construction, but I will leave proving the construction works to you.
First, let us show how to do this in the case that $\mu$ and $\nu$ are measures defined on $\mathbb Z$. It turns out the a joint distribution which works is the one defined by
$$
P(X=x,Y=y)=
\begin{cases}
\min(\mu(x),\nu(y))& x=y\\
\frac{(\mu(x)-\nu(x))^+(\nu(y)-\mu(y))^+}{\|\mu-\nu\|} & x\neq y
\end{cases}\tag 1
$$
Recall that $x^+=\max(x,0)$. I suggest you take the time to carefully verify that this distribution has the correct marginals, and that it satisfies $P(X\neq Y)=\|\mu-\nu\|$. It helps to define $A=\{z\in \mathbb Z\mid \mu(z)\le \nu(z)\}$, and to verify $P(X=z)=\mu(z)$ for $z\in A$ and $z\notin A$, separately.
What about the general case? Things are made tricky by the fact that we cannot use probability mass functions any more. Instead, we will find a common measure that $\mu$ and $\nu$ are absolutely continuous with respect to, and take the Lebesgue-Radon-Nikodym derivative of $\mu$ and $\nu$ with respect to both.
Suppose $\mu$ and $\nu$ are measures on $\Bbb R$ (or any measurable space). Let $\lambda$ be the measure $\mu+\nu$, and let $f,g:\mathbb R\to \mathbb R$ be defined by
$$
f(x)=\frac{d\mu}{d\lambda}\qquad g(y)=\frac{d\nu}{d\lambda}
$$
These derivatives will serve the role of the missing pmfs. We will define a measure $\pi$ on $\mathbb R\times \mathbb R$ as follows. We proceed in two parts (that resemble the two cases in $(1)$).

*

*Consider the function $h(z)=\min(f(z),g(z))$. Then $h(z)\,d\lambda$ is a measure on $\mathbb R$ (where the measure of $A$ is $\int_A h(z)\,d\lambda$). Take the pushforward of this measure under the diagonal inclusion map $\Bbb R\to \Bbb R\times \Bbb R$ to get a measure $\pi_1$ on $\Bbb R\times \Bbb R$ supported on the diagonal.


*Consider the function $$k(x,y)=\frac{(f(x)-g(x))^+\cdot (g(y)-f(y))^+}{\|\mu-\nu\|}.$$ Then $$\pi_2= k(x,y)\mu(dx)\nu(dy)$$ defines a measure on $\mathbb R\times \Bbb R$. To be clear, $\pi_2(A)=\int_A k(x,y)\mu(dx)\nu(dy)$.
Finally, it turns out that $\pi_1+\pi_2$ is a probability measure on $\mathbb R\times \mathbb R$ for which $P(X\neq Y)=\|\mu-\nu\|$.
