A homework problem from Folland Chapter 5, problem 5.25.
If $\mathcal{X}$ is a Banach space and $\mathcal{X}^{\star}$ is separable, then $\mathcal{X}$ is separable.
I tried the following approach: For every $\epsilon >0$ I wanted to show the existence of a linear map from $x_{1},\ldots,x_{n}$ such that for any $x\in\mathcal{X}$ $\| x-L(x_{1},\ldots,x_{n})\|\leq \epsilon$.
Use the Hahn-Banach Theorem:
Taking $f_n$ and $x_n$ as in your hint.
Let $Y$ be the set of all linear combinations of the $x_i$ with rational coefficients.
Suppose $Y$ were not dense in $X$. Then the closure of $Y$ is a proper subspace of $X$, and thus, there is an $f\in X^*$ of norm 1 with $f(Y)=\{0\}$. Then $$ {1\over 2}\Vert f_n\Vert\le|f_n(x_n)| =|f_n(x_n) - f(x_n)| \le \Vert f_n-f\Vert \Vert x_n\Vert =\Vert f_n-f\Vert $$
Take $\Vert f_{n_i}-f\Vert\rightarrow 0$. Then from the above, $\Vert f\Vert=0$, a contradiction.
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$.