"Naturality" in a categorical sense is much more than "not depending on choices", and, also, is essentially unrelated to issues about the Axiom of Choice.
In the example of vector spaces over a field, we can look at the category of _finite_dimensional_ vector spaces, to avoid worrying about using AxCh to find elements of the dual. The non naturality of any isomorphisms of finite-dimensional vectorspaces with their duals resides in the fact that, provably, as a not-hard exercise, there is no collection of isomorphisms $\phi_V:V\rightarrow V^*$ of isomorphisms of f.d. v.s.'s $V$ to their duals, compatible with all v.s. homs $f:V\rightarrow W$.
In contrast, the isomorphism $\phi_V:V\rightarrow V^{**}$ to the second dual, by $\phi_V(v)(\lambda)=\lambda(v)$ is compatible with all homs, as an easy exericise! This latter compatibility is the serious meaning of "naturality".
True, if capricious or random choices play a role, the chance that the outcome is natural in this sense is certainly diminished! But that aspect is not the defining property!
Edit (16 Apr '12): as alancalvitti notes, the ubiquity of adjunctions, and the naturality and sense of "naturality", and counter-examples to naive portrayals, deserve wider treatment at introductory levels. After all, this can be done with almost no serious "formal" category-theoretic overhead, and pays wonderful returns, at the very least organizing one's thinking. Distinguishing "characterization" from "construction-to-prove-existence" is related. E.g., "Why is the product topology so coarse?": to say that "it's the definition" is unhelpful; to take the categorical definition of "product" and _find_out_ what topology on the cartesian product of sets is the categorical product topology is a do-able, interesting exercise! :)
Let $D : \mathbf{fdVec}^{\mathrm{op}}_k \to \mathbf{fdVec}_k$ be the dual space functor, defined by
$$D(V) = V^*, \quad D(f : V \to W) = f^* : W^* \to V^*$$
where $\mathbf{fdVec}_k$ is the category of finite-dimensional vector spaces over a field $k$, and $k$-linear maps.
When we say that $V^*$ is 'not naturally isomorphic' to $V$, we mean that there is not a functor $I : \mathbf{fdVec}^{\mathrm{op}}_k \to \mathbf{fdVec}_k$ with $I \cong D$ such that $I(V)=V$ for all $V$.
So in a sense, you're answering a different question, since what you have defined is a functor $G : \mathbf{fdVec}_k \to \mathbf{fdVec}_k$ with $G \cong \mathrm{id}$ such that $G(V)=V^*$ for all $V$.
What you proved is an instance of a more general fact: given any category $\mathcal{C}$ and any function $(-)^* : \mathrm{ob}(\mathcal{C}) \to \mathrm{ob}(\mathcal{C})$ such that $A \cong A^*$ for all $A \in \mathrm{ob}(\mathcal{C})$, there is a functor $G : \mathcal{C} \to \mathcal{C}$ such that $G \cong \mathrm{id}_{\mathcal{C}}$ and $G(A)=A^*$ for all objects $A$. The proof is identical to the proof you gave.
Even more generally, given a category $\mathcal{C}$, a subcategory $\mathcal{D}$ and a function $(-)^* : \mathrm{ob}(\mathcal{C}) \to \mathcal{ob}(\mathcal{D})$ such that $A \cong A^*$ for all objects $A$, there is an equivalence of categories $G : \mathcal{C} \rightleftarrows \mathcal{D} : I$, where $I$ is the inclusion $\mathcal{D} \hookrightarrow \mathcal{C}$ and $G(A) = A^*$ for all objects $A$ of $\mathcal{C}$. Again, the proof is essentially identical to what you gave, and can be used to prove that every category $\mathcal{C}$ is equivalent to its skeleton.
To give this some more perspective: a consequence of this fact is that $\mathbf{fdVec}_k \simeq \mathbf{Mat}_k$, where $\mathbf{Mat}_k$ has $\{ k^n : n \in \mathbb{N} \}$ as its set of objects, with a morphism $f : k^n \to k^m$ being an $m \times n$ matrix over $k$. Despite all of this, it would be misleading to say that every finite-dimensional vector space over $k$ is 'naturally isomorphic' to $k^n$ for some $n \in \mathbb{N}$, despite the fact that there is a functor $\mathbf{fdVec}_k \to \mathbf{fdVec}_k$ given by $V \mapsto k^{\mathrm{dim}(V)}$ that is naturally isomorphic to the identity functor.
For the same reasons, despite the natural isomorphism you have defined, it would be misleading to deduce that every vector space is 'naturally isomorphic' to its dual.
Best Answer
I think the first step to do is to make clear to yourself, that the notion of a "basis independent isomorphism" only makes sense if the isomorphism is defined "for any vector space". So in my opinion to think from the start that the basic problem is whether "two constructions lead to naturally isomorphic results", which brings you to the language of functors. It is also not necessary that one of the functors is the identity, there are lots of other nice examples. Moreover, there is no need to stick to isomorphisms, you can also think about naturally related results.
To be concrete, consider the identity and the bidual. There is a natural transformation between these functors defined by sending a vector to the corresponding evaluation map. This is an isomorphism for finite demensional spaces but only an injection for general vector spaces, which shows that the answer to question 2 is negative. (More extremely, zero maps define - completely uninteresting - natural transformations between any kinds of functors on vector spaces.) Examples of natural transformations involving two non-trivial functors are provide by the canonical map from $V^*\otimes V$ to $L(V,V)$ which is injective in general and a linear isomorphism if $V$ is finite dimensional. There are lots of similar examples (injective in general and an isomorphism for finite dimensional spaces) related to multilinear algebra, e.g. the natural map from $S^kV^*$ to $(S^kV)^*$.
I am not sure what to say on your question 1. I think the best way is to view a functor as a "construction" defined for general vector spaces and as a natural transformation as a "natural" way to relate two such constructions. The focus on basis independence mainly comes from the fact that using a basis is the major method to violate naturality.