Showing $X^*$ is separable implies $X$ is separable using the Riesz lemma 
If $X$ is a Banach space and $X^*$ is separable, then $X$ is
  separable.

Here, David Mitra mentions a proof using the Riesz lemma. However, I do not fully understand it.

You could also use Riesz' lemma:
Let $Y$ be a  proper closed subspace of the normed space $X$ and
  $0<\theta<1$. Then there is an $x_\theta$ of norm 1 for which $\Vert
 x_\theta-y\Vert>\theta$ for all $y\in Y$. 
If $X$ were not seperable, you could use Hahn Banach to   construct
  uncountably many functionals $f_\alpha\in X^*$ with  $\Vert
 f_\alpha-f_\beta\Vert\ge \theta$ whenever $\alpha\ne\beta$.

If $X$ is not separable, why does that allow us to construct uncountably many separated functionals $f_\alpha$? 
I see why this fact would imply the theorem. Taking a countable dense set and $\epsilon$ balls around each point in that set, we see that two elements of the uncountable set $\{ f_\alpha\}$ must lie in a single ball. But then they are at most $2\epsilon$ apart. Making $\epsilon$ small shows we can find two elements of the set less than $\theta$ apart, a contradiction.
 A: Here is my favorite proof, which I think is simpler than both the one suggested by David C. Ullrich and the one I had given earlier, elaborating on David Mitra’s hint. It uses only the Hahn–Banach theorem, but not Riesz’s lemma. It is based on the hint presented in Exercise 5.25, Folland (1999, p. 160).
If $X^*$ is separable, let $\{f_n\}_{n\in\mathbb N}$ be a countable dense subset of it. By the definition of the operator norm $$\|f_n\|\equiv\sup_{\substack{x\in X\\\|x\|\leq 1}}|f_n(x)|,$$ it is possible, for each $n\in\mathbb N$, to choose some $x_n\in X$ such that $\|x_n\|\leq 1$ and $$|f_n(x_n)|\geq\frac{1}{2}\|f_n\|\tag{$\clubsuit$}$$ (if $f_n=0$, then simply choose $x_n=0$; if $\|f_n\|>0$, use the definition of the supremum).
Let $C\equiv\{x_1,x_2,\ldots\}$. I claim that $\operatorname{span} C$ is dense, which implies that $X$ is separable (see the last claim in my previous post). To see this, suppose, for the sake of contradiction, that $\operatorname{span} C$ is not dense; then $Y\equiv\overline{\operatorname{span} C}$ is a proper closed subspace. By the Hahn–Banach theorem, it is possible to choose $f\in X^*$ such that
\begin{align*}
f(y)=&\,0\quad\forall y\in Y,\\
\|f\|=&\,1;
\end{align*}
see again Theorem 5.8(a) in Folland (1999, p. 159). Since $\{f_n\}_{n\in\mathbb N}$ is dense in $X^*$, there exists some $n\in\mathbb N$ such that $\|f_n-f\|< 1/3$. But then
\begin{align*}
|f_n(x_n)|=|f_n(x_n)-\underbrace{f(x_n)}_{=0}|\leq\|f_n-f\|<\frac{1}{3},\tag{$\diamondsuit$}
\end{align*}
whereas
\begin{align*}
1=\|f\|\leq\|f-f_n\|+\|f_n\|<\frac{1}{3}+\|f_n\|,
\end{align*}
so that $\|f_n\|>2/3$. Putting this into ($\diamondsuit$),
$$|f_n(x_n)|<\frac{1}{3}<\frac{1}{2}\|f_n\|,$$ which contradicts ($\clubsuit$).
A: Third version - maybe this one is right.
Lemma. If $K$ is a separable compact Hausdorff space then $C(K)$ is separable. (And it follows that $K$ is metrizable, but we won't be using that.)
Proof. Wlog $K$ is infinite. Say $p_1,\dots$ are dense, $p_j\ne p_k$ for $j\ne k$. Choose  $f_{j,k}:K\to\Bbb R$, such that $f_{j,k}(p_j)\ne f_{j,k}(p_k)$. The algebra generated by $1$ and the $f_{j,k}$ is separable, and Stone-Weierstrass shows it's dense in $C(K)$. 
Now suppose $X^*$ is separable, and let $K$ be the closed unit ball of $X^*$ with the weak* topology. The lemma implies that $C(K)$ is separable.
But the map $x\mapsto f_x$, where $f_x(x^*)=x^*(x)$, is an isometry from $X$ into $C(K)$. So $X$ is separable.
A: Suppose that $X$ is not separable and fix $\theta\in(0,1)$. Let $\Omega$ be the set of countable ordinals. Fix $\alpha\in\Omega$ and using transfinite induction, suppose that $x_{\beta}\in X$ and $f_{\beta}\in X^*$ have already been defined for all $\beta\in\Omega$ such that $\beta<\alpha$ (if $\alpha=\min\Omega$, simply define $x_{\alpha}\equiv0$ and $f_{\alpha}\equiv 0$).
Let $$X_{\alpha}\equiv\{x_{\beta}\,|\,\beta\in\Omega,\,\beta<\alpha\}.$$
Since $X_{\alpha}$ is countable and $X$ is not separable, it follows that $Y_{\alpha}\equiv\overline{\operatorname{span}X_{\alpha}}$ is a proper closed subspace (I will prove this at the end of the post). Pick any $x_{\alpha}\in X\setminus Y_{\alpha}$ such that
\begin{align*}
\|x_{\alpha}\|=&\,1,\\
\inf_{y\in Y_{\alpha}}\|x_{\alpha}-y\|\geq&\,\theta,
\end{align*} which is possible by Riesz's lemma. Now, using the Hahn—Banach theorem, there exists $f_{\alpha}\in X^*$ such that
\begin{align*}f_{\alpha}(y)=&\,0\quad\forall y\in Y_{\alpha},\\
\|f_{\alpha}\|=&\,1,\\
f_{\alpha}(x_{\alpha})=&\,\inf_{y\in Y_{\alpha}}\|x_{\alpha}-y\|\geq\theta;
\end{align*}
see, for example, Theorem 5.8(a) in Folland (1999, p. 159).
Now, the family $\{f_{\alpha}\}_{\alpha\in\Omega}$ is uncountable (given that $\Omega$ is uncountable and, as the next argument will reveal, $f_{\alpha}$ and $f_{\beta}$ are distinct for distinct $\alpha,\beta\in\Omega$). Suppose that $\alpha,\beta\in\Omega$ and $\alpha\neq\beta$. Without loss of generality, assume that $\beta<\alpha$. Then, $x_{\beta}\in X_{\alpha}\subseteq Y_{\alpha}$, so $f_{\alpha}(x_{\beta})=0$. Also, $f_{\beta}(x_{\beta})\geq\theta$. Therefore, $$\|f_{\alpha}-f_{\beta}\|=\sup_{\substack{x\in X\\\|x\|\leq1}}|f_{\alpha}(x)-f_{\beta}(x)|\geq|f_{\alpha}(x_{\beta})-f_{\beta}(x_{\beta})|\geq\theta.$$

The following claim reveals that if $X$ is not separable, then the subspace $\operatorname{span} X_{\alpha}$ is not dense for any $\alpha\in\Omega$.

Claim: If $C\equiv\{x_1,x_2,\ldots\}\subseteq X$ is a countable subset and $\operatorname{span}C$ is a dense subspace, then $X$ is separable.

Proof: Let $\mathbb S$ be a countable dense subset of the underlying field ($\mathbb R$ or $\mathbb C$, presumably). Define, for each $n\in\mathbb N$, $$L_n\equiv\{q_1 x_1+\ldots+q_n x_n\,|\,q_1,\ldots,q_n\in\mathbb S\}$$ and $L\equiv\bigcup_{n=1}^{\infty} L_n$. It is easy to see that $L$ is countable.
I claim that $L$ is dense. To see this, pick any $x\in X$ and $\varepsilon>0$. Since $\operatorname{span} C$ is dense, there exist some $n\in\mathbb N$ and members of the underlying field $p_1,\ldots,p_n$ such that $$\left\|x-\sum_{m=1}^np_mx_m\right\|<\frac{\varepsilon}{2}.$$ Now, for each $m\in\{1,\ldots, n\}$, pick $q_m\in\mathbb S$ such that $$|p_m-q_m|<\frac{\varepsilon}{2n(\|x_m\|+1)}.$$ Then, $y\equiv\sum_{m=1}^n q_m x_m\in L$ and $$\|x-y\|\leq\left\|x-\sum_{m=1}^np_mx_m\right\|+\left\|\sum_{m=1}^n(p_m-q_m)x_m\right\|<\frac{\varepsilon}{2}+\sum_{m=1}^n|p_m-q_m|\|x_m\|<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon.$$ Hence, $x\in\overline{L}$ and the proof is complete. $\quad\blacksquare$
