The usual way of showing the natural isomorphism between a vector space and its double dual is to prove that the map from $V$ to $V^{**}$ is injective and linear. And since $\dim V = \dim V^*$ and $\dim V^*=\dim V^{**}$, it follows that $\dim V = \dim V^{**}$, which establishes the bijection. I read that showing this isomorphism doesn't require us to choose a basis.
But I've also read that the proof of $\dim V^*=\dim V^{**}$ is similar to $\dim V = \dim V^*$, and proving the latter does require us to choose a basis. So won't establishing that $\dim V^*=\dim V^{**}$ (and hence, in effect, that $\dim V = \dim V^{**}$) also require a choice of basis? That way the proof of the isomorphism requires us to choose a basis at one point, so why is it called a natural isomorphism? Is there supposed to be a basis-free way of showing that $\dim V = \dim V^{**}$?
This sentence is a little bit vague. What you probably read is that defining the isomorphism doesn't require a choice of basis. You can always define $\phi : V \to V^{**}$ by $\phi(v)(f) = f(v)$.
However, you cannot prove that it is a bijection without involving a basis somehow. Since $\phi$ is (in general) only an isomorphism when $V$ is finite-dimensional, you need to use this fact in your argument somewhere, and the dimensionality of a vector space is ultimately defined in terms of the cardinality of a basis for it.