Is a vector space naturally isomorphic to its dual? This question may not be as easy to answer as you think!  Some tangentially-related questions have appeared on math.stackexchange but I'm not really convinced by the answers.
In the sequel I will assume all vector spaces under discussion are finite dimensional.
A vector space is naturally isomorphic to its double dual
In an early linear algebra course  we are told that "a finite dimensional vector space is naturally isomorphic to its double dual".  The isomorphism in question is ${**}_V : V \to V^{**}$, $v^{**}(\phi) = \phi(v)$.  We are told that this isomorphism is "natural" because it doesn't depend on any arbitrary choices.  The notion of "natural", or "independent or arbitrary choice", is made precise via the concept of a category theoretical "natural transformation".  Specifically, the operation $**$ on vector spaces gives rise to a functor whose action on maps is $f^{**} : V^{**} \to W^{**}$, $f^{**}(v^{**}) = f(v)^{**}$.  In fact this is exactly the condition for the naturality square to commute and so ${**}_V$ is indeed a natural transformation (between the identity functor and $**$) which is an isomorphism.
A vector space is naturally isomorphic to its dual!
So far, so familiar.  But there's something that doesn't quite hold up about all this.  Let's adapt the above to show that $V$ and $V^*$ are "naturally isomorphic".  We do this by following exactly the same procedure, replacing $**$ everywhere with $*$.  The only change we have to make is to come up with an arbitrary isomorphism $*_V$ for each $V$.  Other than that, the whole construction goes through unchanged.  Specifically, once we have chosen $*_V$ we define the functorial action on morphisms to be $f^{*} : V^{*} \to W^{*}$, $f^{*}(v^{*}) = f(v)^{*}$.
In particular I have a natural isomorphism between the identity functor and $*$!
Objections to the construction
One could make a few objections to this construction, but they seem to be circular.

*

*"But you admitted that $*_V$ depends on an arbitrary choice!"
I did, but that was informal language.  In what formal sense is it arbitrary?  The notion of "naturality" was supposed to rule out constructions that are arbitrary!


*"Your definition of $f^*$ is invalid.  It depends on $*_V$."
So what?  My definition of $f^{**}$ depends on ${**}_V$ but it is uncontroversial.
"You should have defined $f^{**}(\hat{v})(\phi) = \hat{v}(\phi \circ f)$ and then it's clear that it doesn't depend on $**_V$.  You can't do that for $f^*$."
But your $f^{**}$ is the same as my $f^{**}$!  Is there some formal way of specifying that a functor does not depend on a natural transformation?  And besides, what's the problem if it does?
"It's a problem because it depends on something that depends on arbitrary choice ..."


*"Whilst the functor $**$ is the real double dual functor, $*$ is one you just made up.  It is indeed isomorphic to the identity functor but that doesn't mean anything about 'a vector space being isomorphic to its dual'".
Why not?  I've followed exactly the same recipe for both of them, using the notion of "natural transformation" as I was supposed to.
"Sure, but the result is interesting only in the case of $**$ because your definition of $*$ depended upon arbitrary choice ..."
Conclusion
All attempts to explain why I haven't really shown that a finite dimensional vector space is naturally isomorphic to its dual seem to invoke circular reasoning.
I can only conclude that if the notion of natural transformation is going to be used to formalise the concept of "independent of arbitrary choice" then something needs to be tightened up.  My choice of $*_V$ was indeed arbitrary but it is not ruled out by the notion of natural transformation.
How could we proceed?  Could the absence of choice be used to rule out the construction of $*_V$?  Answers to an earlier question seem to suggest that is an irrelevant issue but in light of the above I'm not convinced.  More generally, does this kind condition perhaps only make sense in a constructive or intuitionistic setting?  I have a clue about how to formalise this condition in type theory via parametricity, so perhaps that is the key!
(This question is similar to an earlier one.  I'm not convinced by the answer.  It seems to be making an objection of the third form above, which seems circular to me.)
 A: There are several things left unsaid. 
First, there is a sense in which "a vector space is naturally isomorphic to its dual" is not even wrong: the usual dual functor is contravariant, not covariant. That is, the identity functor is of the form $\mathbf{Vect} \to \mathbf{Vect}$ while the dual functor is of the form $\mathbf{Vect}^{op} \to \mathbf{Vect}$. Normally, one doesn't ask whether two functors with different domain categories can be isomorphic. 
One way to get around this is by working instead with the core groupoid $\mathbf{Vect}_{core}$, consisting of vector spaces and invertible linear transformations, and defining $\ast: \mathbf{Vect}_{core} \to \mathbf{Vect}_{core}$ to be the functor taking $f: V \to W$ to $(f^{-1})^{\ast}: V^\ast \to W^\ast$, the linear adjoint of its inverse. Then one can ask whether the identity is naturally isomorphic to the covariant dual functor $\ast$. It is not. 
So, the other thing left unsaid is that the dual functor was not given in advance, but cooked up post facto of choosing a bunch of isomorphisms $V \cong V^\ast$. To me, that's "not playing fair". Put differently: put two people in separate rooms and ask them to define a dual functor according to this procedure, and then compare the results. They will never agree on the dual functor, unless by pure accident! 
Analogously, to define the double dual functor, the "fair and square" way would be to define $\ast\ast = \hom(\hom(-, k), k)$ (composing two contravariant dual functors), as opposed to using a conjugation trick 
$$(V^{\ast})^\ast \stackrel{(\delta_V)^{-1}}{\to} V \stackrel{f}{\to} W \stackrel{\delta_W}{\to} (W^\ast)^\ast$$
to define the functor on morphisms, which is effectively what the OP did as the lead-in to his clever question. 
A: You’ve indeed proven the statement: “There exists a functor $\newcommand{\Vect}{\mathbf{Vect}}\Vect \to \Vect$, whose action on objects sends each vector space to its dual, and which is naturally isomorphic to the identity functor.”
The standard theorem about double duals, stated precisely, is not just analogous to this, it’s a stronger statement: “The functor $(-)^{**} : \Vect \to \Vect$, defined as sending each vector space to its double dual and each map to its double dual, is naturally isomorphic to its identity functor.”
In other words, the phrasing “Every vector space is naturally isomorphic to its double dual”, while nice and memorable, isn’t a fully precise statement of the theorem people really mean (and require in applications).  Statements about natural isomorphisms are (at least implicitly) claims about functors, not just functions on objects.
Overall, your observation is a very nice cautionary example against taking informal phrasings too literally; but it doesn’t show any sort of “circularity” in the usual claim that there’s a difference between double and single dualisation.
[This is similar at its core to other answers, but I’m attempting to isolate the main issue a bit more prominently.]

In response, the OP asks: So why is the standard double-dual functor more ‘natural’ than the single-dual functors constructed with choice as in the question?
Here are a few (related) ways in which it’s more natural:


*

*The “standard” dualisation functors (i.e. the double-dual functor, and more primitively, the standard contravariant single-dual functor) extend to functors on bundles (more generally, sheaves) of vector spaces/modules.

*The “standard” functors are (co-?)laxly natural with respect to monoidal closed categories. Every monoidal closed category (e.g. the category of modules over any ring, or of vector bundles over some space) carries evident versions of these functors; and suitable functors between such categories (e.g. induced by ring homomorphisms, or change of base) will commute with the standard dualisation functors up to natural comparison maps; and when the functor is an equivalence of symm. mon. cats, these comparison maps will be isomorphisms.

*The “standard” functors should be (co-?)laxly natural with respect to maps between different “mathematical universes”/“models of set theory”.  I won’t give a precise statement here; it would probably be easiest to do this in terms of toposes, but I’m fairly confident it should also be possible to give a version in terms of models of ZFC.  This is a rather more involved sort of statement than the other properties above, but is perhaps the closest to the intuitive idea that these constructions are “canonical” rather than “arbitrary”.
(I’m not certain that the “arbitrary” functors the OP defines using choice don’t also satisfy these naturality properties — I don’t remember or see off the top of my head arguments/counterexamples showing that they can’t — but I’m fairly confident they don’t, and that fairly familiar techniques should suffice to show it.)
A: I think that the issue boils down to a problem with the meaning that is generally ascribed to isomorphic objects. Typically it is said that isomorphic objects are "identical" in the sense that they are interchangeable i.e. "a theorem proved about one group is true for all isomorphic groups" 
But isomorphic objects are not always interchangeable. Ultimately it depends on what additional structure/relationships you need to consider hence the reason that the categorical definition of natural includes functors. Natural isomorphisms are about describing higher levels of identity and interchangeability than standard isomorphisms.
Saying "arbitrary choices" implies that a non-arbitrary choice would be OK but actually the phrase really means that additional data/structure is required which limits the interchangeability that is possible. In the case of the $V\rightarrow V^{**}$ isomorphism you require a specific basis for $V$ in order to define the mapping in $V^*$. However if you already have an inner product defined then the dual basis can be defined with no additional inputs and in this case $V^{*}$ is genuinely interchangeable with $V$ similar to the duality between theorems in projective geometry when swapping points and lines.
A: To get to the point quickly first, the OP has definitely constructed a natural isomorphism (with some steps missing that I fill in below.) However, it is misleading to call it "a natural isomorphism between a vector space and its dual" because the interest in the dual space construction on finite-dimensional vector spaces is not simply forming $V^*$ from $V$ for all $V$, but also forming the dual of every linear map $f \colon V \rightarrow W$. The OP's construction has nothing to do with dual maps and that's why it is of no interest in practice. That is not a comment on logic, but on what people care about.
Now for some more details. We'll generalize the OP's construction to all categories. In a category $C$, pick (arbitrarily) for each object $X$ of $C$ an isomorphism $T_X$ with domain $X$. (The OP took for $C$ the category of finite-dimensional vector spaces over a field $k$ and for $T_V$ an arbitrary isomorphism of $V$ with its $k$-dual space.) I'll build a functor from these choices. For each object $X$ set $T(X) = T_X(X)$ to be the target object of $T_X$ and for each morphism $f \colon X \rightarrow Y$ in $C$ define the morphism $Tf \colon T(X) \rightarrow T(Y)$ to be the one making the "obvious diagram" commute (we want to turn $X$ into $T(X)$ via $T_X$ and $Y$ into $T(Y)$ via $T_Y$): we want $Tf \circ T_X = T_Y \circ f$, and the only way that holds is by defining $Tf = T_Y \circ f \circ T_X^{-1}$.  Using the inverse of $T_X$ in the definition of $Tf$ is how we use the condition that every $T_X$ is an isomorphism. 
When $C$ is the category of finite-dimensional vector spaces over a field $k$, the OP never said how to define the effect of the OP's construction on linear maps, but I have done this above and I'll be more explicit about it: for each linear map $f \colon V \rightarrow W$ of finite-dimensional $k$-vector spaces, define the $k$-linear map $f^* \colon V^* \rightarrow W^*$ between dual spaces to be $*_W \circ f \circ *_V^{-1}$. Unlike what the OP wrote, this is not "following exactly the same proceduce" as with double duality, since double duality involves ideas that are nowhere in the OP's construction. (What I write here as $f^*$ has nothing to do with the notion of the dual map of $f$, since it depends on the arbitrary isomorphisms $*_V$ and is going in the opposite direction to the dual a $k$-linear map from $V$ to $W$.) 
It is easy to check that $T({\rm id}_X) = {\rm id}_{T(X)}$, which by the definition of our notation is ${\rm id}_{T_X(X)}$, and for morphisms $f \colon X \rightarrow Y$ and $g \colon Y \rightarrow Z$ we have $T(g \circ f) = Tg \circ Tf$ as morphisms from $T(X)$ to $T(Z)$.  Thus a choice, for each object $X$ of $C$, of an isomorphism $T_X$ with domain $X$ has given us a covariant functor $T$ from $C$ to itself. 
There is a natural isomorphism from the identity functor ${\rm id}_C$ on $C$ to the functor $T$, namely the collection of morphisms $\{T_X \colon X \rightarrow T_X(X)\}$ fits the definition of a natural isomorphism. The definition of a natural isomorphism does not depend logically on the intuitive idea of "no arbitrary choices". To the contrary, the definition of a natural isomorphism is itself a collection of choices, and they may very well be to some extent "arbitrary". All the definition requires is that everything behaves functorially (and has an inverse).
Todd Trimble says in his answer that a problem with the OP's construction is that if you put two people in separate rooms and ask them to define a dual functor according to the OP's procedure then the two people will almost certainly not agree on the result. (EDIT: From Todd's comment below I realized that he had actually raised a different objection, where the functors themselves turn out to be different, but the point I am raising here still stands.) That isn't a fair objection, since even in situations where there is an agreed-upon natural isomorphism between two functors, it need not be the only natural isomorphism between those two functors. For example, on the category of finite-dimensional real vector spaces we have the standard natural isomorphism from the identity functor to the double dual functor, but there are many more natural isomorphisms between those two functors: for each $a \in \mathbb R^\times$ and finite-dimensional real vector space $V$ define the linear map $T_a \colon V \rightarrow V^{**}$ by $(T_a(v))(\varphi)  = a\varphi(v)$ for $v \in V$ and $\varphi \in V^{*}$. Then $T_a$ is a natural isomorphism from the identity functor to the double dual functor, with $T_1$ being the standard natural isomorphism. If you ask two people who only think purely logically to come up with a natural isomorphism between the identity and double dual functors on finite-dimensional real vector spaces then one of them might come up with $T_5$ and the other with $T_\pi$. There is no purely logical reason their results have to agree, but that doesn't mean the identity and double dual functors are not naturally isomorphic.  And what I described here is not specific to vector spaces over $\mathbb R$: the same way of building extra natural isomorphisms besides a standard one works for finite-dimensional vector spaces over each field $k$ other then $\mathbb F_2$ (since $\mathbb F_2^\times = \{1\}$).
The OP asks at the end of the post what needs to be tightened up to get around the OP's construction of a natural isomorphism between $V$ and $V^*$. What needs to be tightened up is that the idea of "a natural isomorphism between $V$ and $V^*$" is inherently sloppy: the OP paid absolutely no attention to the dual map construction that is an essential part of what mathematicians use when they work with dual spaces. Category theory teaches us that morphisms are just as important as objects, and what mathematicians care about with duality is not simply the formation of $V^*$ from $V$ but the formation of the standard dual map $W^* \rightarrow V^*$ of each linear map $V \rightarrow W$. The OP started off only with a construction on objects (passing from $V$ to $V^*$ for all finite-dimensional $k$-spaces $V$). Nowhere in the OP's construction of a natural isomorphism did the standard dual map ever appear, and that's why the OP's natural isomorphism from the identity functor to another functor is of no practical value: what matters is not having a natural isomorphism alone, but having a natural isomorphism between two functors that are of actual interest. The functor built by the OP is not the dual functor (pay attention to morphisms, not just objects). And if you want to extend linear algebra constructions like dual spaces or tensor powers to vector bundles, you're going to run into problems if your linear algebra constructions use arbitrary choices instead of being "coordinate-free".
The OP is welcome to prove theorems about the OP's arbitrary functor, which has a natural isomorphism to the identity functor, but I doubt anyone would find the results worthwhile. Ultimately the utility of a definition in math depends on doing something that a community of people finds interesting, and that is a matter of human judgment, not pure logic. 
A: There are two more parts of this story (of dual spaces) that I personally find quite useful in giving me some intuition about this sort of question.  So I share them in the hopes that they will be useful to others.  They also show that there cannot be any isomorphism (even in the finite dimensional case) between a vector space and its dual, if we take vector spaces over arbitrary division rings.
First is the fact that given rings $R$, $S$, and $T$, and two bimodules $_SM_R$ and $_TN_R$, then the set of right $R$-module homomorphisms ${\rm Hom}(_SM_R, \,_TN_R)$ is automatically a left $T$ and right $S$ bimodule, via the action $$(t\varphi s)(m)=t\cdot \varphi(s\cdot m).$$  The right $R$-module structure is "used up"---there really is no canonical $R$-module structure on the hom set anymore (when $R$ is an arbitrary ring).
Second, when working with modules or vector spaces, actions from one side can be significantly different than on the other.  Very strange things can happen.  For instance, if $D$ is a division ring then you can have a $D$-$D$-bimodule $M$ which is finite dimensional on one side and infinite dimensional on the other!
So, with all that said, consider our situation.  Let $D$ be a division ring.  Consider a (finite, if you like) right $D$-module $V_D$ (i.e., a vector space). The dual space is $V^{\ast}={\rm Hom}(V_D,D_D)$.  There is no right $D$-module structure on $V^{\ast}$, but there is a left $D$-module structure coming from the fact that $D_D$ is really a $D$-$D$-bimodule.  So, in a very strong sense (especially when $D$ is noncommutative) it is wrong to even claim that there is an isomorphism of $V_D$ with $_DV^{\ast}$, because they live in completely different places (i.e., right vs. left modules).
We can, of course, make $_DV^{\ast}$ into a right $D^{\rm op}$-module (where $D^{\rm op}$ is the opposite ring of $D$).  When $D$ is commutative then $D^{\rm op}=D$, so $V^{\ast}$ becomes a right $D$-module in this case.  But this is an "accident" of commutativity, so to speak.
