Separability of Banach Spaces
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$.
This is a rather indirect proof.
We know from Alaoglu's theorem that $B(H^{*})$ is weak-star compact. If we can prove $H^{*}$ is weak star metrizable, then we can show $H$ is separable. If I am not mistaken, proving $B(H^{*})$ is metrizable is enough to show $H^{*}$ is metrizable. By Urysohn's metrization theorem, a compact space is metrizable if and only if it is Hausdauff and second countable. But I think if $H$ is a Banach space over $\mathbb{C}$ or $\mathbb{R}$, then $H^{*}$ must be Hausdauff as functionals separate points.
We still need to show $H^{*}$ is second countable. Given any open set $U$ in $H^{*}$, since $H^{*}$ is separable there is a countable subset $f_{n}$ dense in $U$. Let $x_{n}\not \in ker(f_{n})$ such that $f_{n}(x_{n})=1$, $f_{n}(x_{m})=0$. This is possible since $\bigcup \ker(f_{n})\not=H$ by Baire Category Theorem (each one of them is nowhere dense). Now the set $$U_{n,m}=\{f:\langle f,x_{n}\rangle<\frac{1}{m}\}$$must somehow cover $U$. So $H$ must be separable.