1) It is not so hard to construct an $f \in E^* \setminus \operatorname{span}\{e_i^*\}_{i \in I}$. To do this, notice it is enough to define $f(e_i) = 1$ for each $i$ and extend by linearity. Then if $f = \sum_{j} a_j e_j^*$ then $f(e_i) = 1$ implies that $\alpha_i = 1$. But if $f \in \operatorname{span}\{e_i^*\}_{i \in I}$ then all but finitely many of the $\alpha_j$ are $0$ so we see that $f \not \in \operatorname{span}\{e_i^*\}_{i \in I}$.
2) In general, no. For example, let $c_0$ be the space of sequences with finitely many non-zero entries equipped with the supremum norm. Then $c_0 = \operatorname{span}\{e_i\}_{i \in \mathbb{N}}$ where $e_i$ is the sequence with $1$ in the $i$-th place and $0$ elsewhere. It is well known that $c_0' \simeq \ell^1$. However we cannot have $\ell^1 = \operatorname{span}\{e_i^*\}$ because $\ell^1$ is a Banach space and hence cannot have a countable basis (see here).
3) Doing this for an arbitrary vector space relies on the axiom of choice (or more precisely the assumption you can find a basis). Let $X$ be your infinite dimensional normed space and suppose $\{e_i: i \in \mathbb{N}\}$ is a linearly independent set such that $\|e_i\| = 1$. Extend it to a basis $\{e_i: i \in \mathbb{N}\} \cup \{d_i: i \in I\}$ for $X$. Then define $f(e_i) = i$ and $f(d_i) = 0$ and extend $f$ by linearity to all of $X$ so that $f \in X^*$. Since $f(e_i) = i$, $f \not \in X'$.
