edit I'm leaving the "answer" as is but now I realize that it doesn't get that far. I think it gives a subspace $W' \subset W=V^{\ast}$ with an uncountable basis. And $(W')^{\ast}$ includes but is much bigger than the set of all $\widehat{x}$. Maybe that is not that helpful.
No, it doesn't require the axiom of choice. It takes choice to show that $W$ has a basis but not to show that it has a subspace that has an uncountable basis. I remembered that I once saw a great construction due to Von Neumann so I Googled it and ended up at explicit big linearly independent sets. I suggest checking out the web site!
I think that should do it. Well actually Von Neumann's set is algebraically independent. Earlier in the answer it is pointed out that $T_r = \sum_{q_n < r} \frac{1}{n!}$ (where $q_0, q_1, \ldots$ is an enumeration $\mathbb{Q}$) is independent over $\mathbb{Q}$. So write each $T_r$ in binary and convert it into a $0,1$ element of $W$.
