A similar proof in spirit to Shuhao Cao's, using geometric calculus.
In GC it's easier not to deal with the cross product or curl, but with the more fundamental entities: the generalized dot and wedge products, and the corresponding interior and exterior derivatives.
The basic relation needed to relate curl/cross product to these other operations is $a \times b = -i (a \wedge b)$. The quantity $i$ is called the unit pseudoscalar; it might also be called a volume form, and using it finds for you the Hodge dual of a given object. Here, that duality is captured in the natural multiplication operation called the geometric product. I won't worry over too many of these details; just know that $i$ commutes with all objects in 3d, and $i^2 = -1$.
Hence we see that
$\begin{align*}(\nabla \times A) \times A &= -i [(\nabla \times A) \wedge A] \\ &= -i [(-i \{\nabla \wedge A\}) \wedge A] \\&= i^2 (\nabla \wedge A) \cdot A\end{align*}$
where in the last step we've used the duality of the dot and wedge: $(iX) \wedge Y = i (X \cdot Y)$.
To analyze $(\nabla \wedge A) \cdot A$, we can use an analogue of the BAC-CAB rule.
$(\nabla \wedge A) \cdot A = \dot \nabla (\dot A \cdot A) - (A \cdot \nabla) A$
But by symmetry, $\dot \nabla (\dot A \cdot A) = \frac{1}{2} \nabla (A \cdot A)$. This basically completes the proof; in fact, nothing really exotic has been done except changing notation and using the BAC-CAB rule! Certainly this was a surprise to me, or else I never would've bothered to change notation in the first place.