The proof every vector space has a basis uses the axiom of choice; the proof is similar to that of the well-ordering theorem. Let $f$ be a choice function on the set of nonempty subsets of $V$. By transfinite recursion we define for ordinals $\alpha$ a function $e\left(\alpha\right) :=f(V\backslash\text{span}\left\{ e\left(\beta\right)|\beta\in\alpha\right\} )$. This definition malfunctions iff the argument of $f$ is empty, i.e. we define $e\left(\alpha\right)$ until the span covers all of $V$. This is guaranteed to eventually happen, since otherwise one could inject the ordinals into the set $V$.
Replacing two basis elements $e_1,\,e_2$ with $a e_1\pm b e_2,\,a\neq 0\neq b$ is the usual way of showing a basis isn't unique. For this argument to work, we need the same span from this alternative. Certainly $2a e_1,\,2b e_2$ are included. In fields of characteristic 2, such as $\mathbb{F}_2$ (discussed in the above comments), we can't then divide by $2a,\,2b$ to finish the proof, because $2:=1+1=0$.
For a subspace $T\subseteq V'$ define $T^0 := \{v\in V\,|\, \varphi(v) = 0\text{ for all $\varphi\in T$}\}$ (which is the same as your definition under the identification $V = V''$). In your case, we have $\Gamma^0 = S$.
Then we have $\dim V = \dim U + \dim U^0$ for each subspace $U\subseteq V$: Take a basis $u_1,\dotsc,u_d$ of $U$ and complete it to a basis $u_1,\dotsc,u_n$ of $V$. Denoting by $u'_1,\dotsc,u'_n$ the dual basis, it is easy to see that $U^0$ is spanned by $u'_{d+1},\dotsc,u'_n$, which proves the claim.
Likewise, we have $\dim V' = \dim T + \dim T^0$ for any subspace $T\subseteq V'$. More precisely, let $\varphi_1,\dotsc,\varphi_d$ be a basis of $T$ and complete it to a basis $\varphi_1,\dotsc,\varphi_n$ of $V'$. Then it follows directly from the definitions that $T^0 = \bigcap_{i=1}^d \ker\varphi_i$. It remains to check that $\dim \bigcap_{i=1}^d \ker \varphi_i = n-d$. Indeed, putting $W_j = \bigcap_{i=1}^j \ker\varphi_i$, for $j=1,\dotsc,d$, we obtain an increasing chain
$$
0 = W_n \subset W_{n-1} \subset\dotsb \subset W_1 \subset V.
$$
Since obviously $\dim W_j \ge \dim W_{j+1} \ge \dim W_j-1$, for all $j$, and $\dim W_1 = n -1$, we must in fact have $\dim W_j = n-j$. In particular,
$$
\dim T^0 = \dim \bigcap_{i=1}^d\ker\varphi_i = \dim W_d = n-d = \dim V' - \dim T.
$$
Now, it follows that $T^{00} = T$ for $T\subseteq V'$: $T\subseteq T^{00}$ is clear and both have the same dimension, because of
$$\dim T = \dim V' - \dim T^0 = \dim V - \dim T^0 = \dim T^{00}.$$
With this, we conclude $\Gamma = \Gamma^{00} = S^0$ (using $\Gamma^0 = S$ for the last equality).
Best Answer
Everything you said is correct, but the fact that the dimension of $V$ is finite is crucial, for it says that the map $$V \ni v \mapsto (f \mapsto f(v))\in V^{**}$$is an isomorphism.
If $B$ is a basis for $V$, one constructs the associated dual basis $B^*$. Repeating this process with $V^*$ and $B^*$ playing the roles of $V$ and $B$ gives us the dual basis $B^{**}$ of $B^*$, in $V^{**}$. Hit this basis $B^{**}$ with the isomorphism $V^{**}\to V$. You get, wait for it... that's right, $B$.
So there is a "natural" (in a very precise categorical meaning) correspondence between bases for $V$ and bases for $V^*$.