Finite-dimensional space naturally isomorphic to its double dual?

The fact that $\alpha_V$ has an inverse is indeed less natural. As you know, $\alpha_V$ is a well defined natural embedding also when $V$ is infinite dimensional, but then it does not have an inverse usually. This implies that the construction of the inverse has to be somewhat less elegant than that of $\alpha_V$.

However, choosing a basis does not necessarily mean that the construction is not natural. One very important question is whether the construction depends on the choice or not. In our case, it is definitely independent of choice of basis, since any isomorphism has a unique inverse. This means that the inverse is natural after all.

For comparison, this is not the case when constructing an isomorphism $V\to V^*$. In this case, the isomorphism does depend on choice of basis.

Note that many natural constructions involve some choice, and then one needs to show the choice does not effect the result. One simple example is the universal property of the quotient. Take abelian groups for instance. Say you have a homomorphism $\varphi:A\to B$, such that $\varphi(C)=0$ for some subgroup $C\subset A$. So $\varphi$ induces a homomorphism $\tilde{\varphi}:A/C\to B$. How does one construct this homomorphism? Given an element in the quotient $A/C$, one has to choose a representative in $A$. But of course, the choice does not change the image, and so this construction is universal.

You are not required to exhibit an inverse, only to prove existence. Thus, in the finite case, where the always-injective map to the second dual is actually a bijection, by dimension-counting, you can prove existence of an inverse without choosing anything: given $w$ in the second dual, there is unique $v\in V$ mapping to $w$. "Defined" $\alpha^{-1}(w)=v$.

It is true that defining "dimension" involves showing that the cardinalities of any two bases are the same, ... but it is not always the case that things need to be defined via a basis and then shown independent of the basis.