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 say it is "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 put two people who only think purely logically in separate rooms and ask them 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 that happens to be naturally isomorphic to the identity functor, but I doubt anyone would find the results worthwhile. Ultimately definitions in math depend on doing something interesting with them, and that is a matter of human judgment, not pure logic.