The proofs I've found of the fact that $**\alpha=(-1)^{k(n-k)}\alpha$, or, equivalently, the fact that the Hodge star is an isometry, all use an orthonormal basis. Is there a basis-free proof of either of these facts directly from the definition of the Hodge star by
$$\alpha\wedge*\beta=\langle\alpha,\beta\rangle\mathrm{vol}?$$
On
$ \newcommand\Ext{{\bigwedge}} \newcommand\form[1]{\langle#1\rangle} \newcommand\Cl{\mathrm{Cl}} \newcommand\rev\widetilde $We consider the Hodge star on the exterior algebra $\Ext V$ arising from $I \in \mathop{\Ext^{\!n}}V$ and the non-degenerate symmetric bilinear form $\form{\cdot,\cdot}$ on $V$ which extends to $\Ext V$ where $\form{I, I} = \pm1$. We assume $V$ is a finite-dimensional vector space over a field of characteristic $\not=2$. The bilinear form gives rise to a Clifford algebra $\Cl(V)$ which is canonically isomorphic to $\Ext V$, so we may consider $I$ as an element of $\Cl(V)$ and $\form{\cdot,\cdot}$ as a bilinear form on $\Cl(V)$. It is a fact that $$ \form{A, B} = \form{\rev AB}_0,\quad A, B \in \Cl(V) $$ where $\rev A$ is the reverse of $A$ (the main anti-involution which fixes vectors and reverses all products), $\rev AB$ is the Clifford product, and $\form{\cdot}_0$ is the scalar part (i.e. grade 0 projection). It follows from the definition of the Hodge star and well-known properties of the Clifford product that when $A$ and $B$ are $k$-vectors we have $$ A\wedge\star B = \form{\rev AB}_0I = \form{A\rev B}_0I = A\wedge(\rev BI). $$ Since this is true for every $A$, we see $$ \star B = \rev BI, $$ and this equation is true for all $B \in \Cl(V) \cong \Ext V$ since it is true for each grade and is linear in $B$.
If $\form{\cdot,\cdot}$ is Euclidean then $$ \rev II = \form{\rev II}_0 = \form{I, I} = 1 $$ and also $I^2 = -1$. The fact that the Hodge star is an isometry is now trivial: $$ \form{\star A, \star B} = \form{\rev{\rev AI}\rev BI}_0 = \form{\rev IA\rev BI}_0. $$ At this point, it is well-known that $X \mapsto \rev IXI$ is an orthogonal transformation (this being one of the main features of Clifford algebras; $I$ is an element of the Pin group, more specifically the Spin group). We could also argue algebraically to get $$ \form{\rev IA\rev BI}_0 = \form{A\rev BI\rev I}_0 = \form{A\rev B}_0 = \form{A, B}. $$ The double Hodge star formula is also trivial; if $B$ is a $k$-vector $$ \star\star B = \rev{\rev BI}I = \rev IBI = (-1)^{n(n-k)}\rev IIB = (-1)^{n(n-k)}B. $$ I will explain this it bit further. Let e.g. $[B] = \{x \in V \;:\; x\wedge B = 0\}$ be the subspace represented by $B$. $I$ factors as $B^\perp B$ where $[B^\perp] = [B]^\perp$, meaning that $I = B^\perp B = B^\perp\wedge B$. (Clearly, $B^\perp$ is proportional to $\star B$.) The grade of $B$ is $k$ and that of $B^\perp$ is $n-k$ so $$ BI = BB^\perp B = (B\wedge B^\perp)B = (-1)^{n(n-k)}(B^\perp\wedge B)B = (-1)^{n(n-k)}IB. $$ Note that the double Hodge star formula relies on $\form{\cdot,\cdot}$ being Euclidean, and changes for other bilinear forms.
On
As remarked above by Yuri Vyatkin, the Hodge * being an isometry is more or less the same as the double Hodge being $(-1)^{k(n-k)}$ times the identity.
This is my attempt to prove it is an isometry (well,"isometry like": the sign of the innerproduct/nondegenerate symmetric bilinear form is allowed to flip sign) without using a basis. Only for simple (fully decomposable) $k$-vectors however. By (multi)linearity it should work on all of $\Lambda^k(V)$. I guess this is how many properties on $\Lambda(V)$ are defined.
Consider the Grassmann complement. Given a special $n$-covector $\omega$ and also a privileged $n$-vector $\Omega$, the Grassmann complement is a map $*:\Lambda^k(V)\to\Lambda^{n-k}(V^*)$ defined by $$i_{a_1\wedge\dots\wedge a_k}\omega(u_1,\dots,u_{n-k})=\omega(a_1,\dots,a_k,u_1,\dots,u_{n-k}). $$ Similarly $*:\Lambda^k(V^*)\to\Lambda^{n-k}(V)$ - with $\Omega$ instead of $\omega$. (Both directions being called * as well as the Hodge dual denoted * is confusing. Sorry.) The action of a simple $k$-covector on a simple $k$-vector is given by the determinant $$ \langle a_1\wedge\dots\wedge a_k,\alpha_1\wedge\dots\wedge \alpha_k\rangle =\left|\begin{array}{ccc} \langle a_{1},\alpha_{1}\rangle & \cdots & \langle a_{1},\alpha_{k}\rangle\\ \vdots & \ddots\\ \langle a_{k},\alpha_{1}\rangle & & \langle a_{k},\alpha_{k}\rangle \end{array}\right|.$$ To find $\langle *(\alpha_{1}\wedge\dots\wedge\alpha_{k}), *(a_{1}\wedge \dots\wedge a_k)\rangle$, we can use that the adjoint of contraction with $\alpha\in V^*$ is wedging with $\alpha$. $$ \langle *(\alpha_{1}\wedge\dots\wedge\alpha_{k}), *(a_{1}\wedge \dots\wedge a_k)\rangle=\langle i_{\alpha_{1}\wedge\dots\wedge\alpha_{k}}\Omega, i_{a_{1}\wedge \dots\wedge a_k} \omega\rangle\\ =\langle \Omega,\alpha_{1}\wedge\dots\wedge\alpha_{k}\wedge i_{a_{1}\wedge \dots\wedge a_k} \omega\rangle $$ We also need $i_a (\sigma \wedge \tau)=(i_a \sigma)\wedge \tau + (-1)^{\deg \sigma}\sigma\wedge i_a \tau $ ("$i_a$ is an anti-derivation"). For $k=1$, we simply get $$ \alpha\wedge i_a\omega = -i_a(\alpha\wedge\omega)+\langle a,\alpha\rangle \omega=\langle a,\alpha\rangle \omega. $$ Next, $k>1$. By bringing the $i_{a_k}$ to the front in the LHS below, using the anti-derivational character of $i_a$ you get an expansion of the determinant above. (When working with orthonormal/dual bases this step is particularly easy). We get $$ \alpha_{1}\wedge\dots\wedge\alpha_{k}\wedge i_{a_{k}}\dots i_{a_{1}}\omega=\langle a_1\wedge\dots\wedge a_k,\alpha_1\wedge\dots\wedge \alpha_k\rangle\omega $$ So $$ \langle a_1\wedge\dots\wedge a_k,\alpha_1\wedge\dots\wedge \alpha_k\rangle\langle \Omega,\omega\rangle =\langle *(\alpha_{1}\wedge\dots\wedge\alpha_{k}), *(a_{1}\wedge \dots\wedge a_k)\rangle. $$ In the case of the Hodge * dual we have the volume form $\omega=\sqrt{|g|}dx^1\wedge\dots\wedge dx^n$ and also a special $\Omega=\varphi(\omega)$, where $\varphi$ is the Riesz isomorphism (is it called that on Minkowski space too?). We should have $\langle\Omega,\omega\rangle=\sqrt{|g|}\cdot\sqrt{|g|}/\det{g}=\text{sign}(\text{metric})$
(The Clifford answer by Nicholas Todoroff looks pretty neat to me btw. I don't fully understand it.) First post, can't comment.
Let me make just a partial contribution as an answer, as it is too long for a comment.
Assuming we know that $\star$ is an isometry, and taking the identity in the question as a definition,
$$ \begin{align} \langle \alpha, \beta \rangle \mathrm{vol} & = \langle \star \alpha, \star \beta \rangle \mathrm{vol} = \star \alpha \wedge \star \star \beta = (- 1)^{k(n-k)} \star \star \beta \wedge \star \alpha \\ & = (- 1)^{k(n-k)} \langle \star \star \beta , \alpha \rangle \mathrm{vol} = (- 1)^{k(n-k)} \langle \alpha , \star \star \beta \rangle \mathrm{vol} \end{align} $$
so, we get the desired fact from the non-degeneracy of the metric.
Conversely, if we know, that $**\alpha=(-1)^{k(n-k)}\alpha$ holds, then, considering that
$$ \langle \star \alpha, \star \alpha \rangle \mathrm{vol} = \star \alpha \wedge \star \star \alpha = (-1)^{k(n-k)} \star \alpha \wedge \alpha = \alpha \wedge \star \alpha = \langle \alpha, \alpha \rangle \mathrm{vol} $$
which implies that $\star$ is an isometry.
Now, we probably want to prove in a coordinate-free manner, that $\star$ is an isometry. However, it looks like a delicate matter, as we can see from the discussion around this question, so I feel that I need to take a timeout :)