Let's actually follow suggestion by @idm and use the Grassmann identity to make a proof.
$$a\times (b\times c) = b (a \cdot c) - (a\cdot b) c.\qquad (1)$$
Let us assume, that we know, that it is true for $a$, $b$, $c$ being vectors with real numbers as their elements. The rigorous proof of the identity
$$\nabla \times (\nabla \times A)=\nabla (\nabla \cdot A)-\nabla^2 A\qquad (2)$$
can be constructed from (1) by looking the basic facts about how polynomials work.
Polynomial $p$ in variables $x_1,\dots,x_n$ is a formal expression of the form
$p=\sum_{k_1,\dots,k_n} a_{k_1,\dots,k_n} x_1^{k_1}\dots x_n^{k_n}$, where there are only finitely many terms with nonzero $a_{k_1,\dots,k_n}$. In each sum $k_i$ goes over all nonnegative integers.
The terms in this sum are called its monomials, and real numbers $a_{k_1,\dots,k_n}$ are called coefficients. Denote with $p|_{x_n=b}$ the polynomial, obtained from $p$ by replacing $x_n$ with a real number $b$ (so it becomes a polynomial in $n-1$ variables).
Claim 1. Let $p$ be a polynomial in $x_1,\dots,x_n$, and let $p|_{x_n=b}=0$. Then $p=(x_n-b)q$ for some polynomial $q$.
Proof. Replace $x_n$ with $y+b$ in $p$. You will get a polynomial $\widetilde p$ in $x_1,\dots,x_{n-1},y$. By assumption $\widetilde p|_{y=0}=0$, so all monomials of $\widetilde p$ have now a nonzero power of $y$. Thus we can write $\widetilde p = y \widetilde q$ and replace back $y$ with $x_n-b$. $\square$
Claim 2. Let $p$ be a polynomial in $x_1,\dots,x_n$, which is not 0 (i.e. it has at least 1 nonzero coefficient). Then it is not zero at some point $x_1=a_1,x_2=a_2,\dots,x_n=a_n$.
In other words, nonzero polynomial is nonzero as a function.
Proof.
You prove this by induction in $n$. For $n=0$ the claim is trivial.
Induction step. Let $d$ be the degree of $p$ with respect to variable $x_n$ (i.e. the highest k_n in the term $ax_1^{k_1}\dots x_n^{k_n}$ with nonzero $a$, appearing in $p$). We want to find $a_n$, such that after substituting it for $x_n$ we get a nonzero polynomial of $x_1,\dots,x_{n-1}$. Then we can apply the induction hypothesis to find $a_1,\dots,a_{n-1}$. Assume to the contrary, that we can't find such $a_n$. Then for every real number $b$ we get $p|_{x_n=b}=0$. Find any $d+1$ different real numbers $b_0,\dots,b_d$. By applying claim 1 $d+1$ times to $p$, write $p=(x_n-b_0)(x_n-b_1)\dots(x_n-b_d)q$. By assumption $q$ is nonzero (otherwise $p$ will be zero). So degree of $p$ in $x_n$ is at least $d+1$. Contradiction. $\square$
Claim 3. If we open the brackets in each of the 3 components of (1) (by only using definitions of $\times$ and $\cdot$, distributive law, commutativity and associativity of multiplication and addition), then we will get the same expression on the left hand side, as on the right.
Proof. Suppose for one of the 3 components we get expression $L$ on the left, and $R$ on the right, and these are not the same. Then $L-R$ is a nontrivial polynomial in 9 variables. But according to Grassmann identity, it is zero for all the values of these 9 variables. So by claim 2 it should be identically zero. $\square$
Derivatives $\partial/\partial x$, $\partial/\partial y$, $\partial/\partial z$ and components of $A$ satisfy all the properties we needed to show (1), i.e. all the properties, listed in claim 3, except we can't permute components of $A$ with derivatives.
But note, that while expanding $(1)$ we can always keep $c$ on the far right in each product. So we don't need to use associativity of multiplication to permute components of $c$ with components of $a$ and $b$.
So we can apply (1) to show (2) rigorously.