prove $\frac{1}{2}\mathbf{\nabla (u \cdot u) = u \times (\nabla \times u ) + (u \cdot \nabla)u}$ using index notation

So, your first step is indeed correct, but the one you are not sure about is wrong. You are probably confused by your own notation, I prefer to write $\partial_i=\frac{\partial}{\partial x_i}$ instead of $\partial x_i$. And remember that repeated indices are being summed over, so e.g. $u_ju_j=\mathbf{u}\cdot\mathbf{u}$. Given that, you have \begin{equation} u_j\partial _i u_j-u_j\partial_j u_i =(1/2)\partial_i(u_j u_j)-(\mathbf{u}\cdot \nabla)u_i =(1/2) \partial_i (\mathbf{u}\cdot\mathbf{u})-(\mathbf{u}\cdot \nabla)u_i, \end{equation} which (taking into account your earlier work) is the $i$-th component of the equation \begin{equation} \mathbf{u}\times(\nabla\times \mathbf{u})=\frac{1}{2}\nabla(\mathbf{u}\cdot\mathbf{u})-(\mathbf{u}\cdot \nabla)\mathbf{u} \end{equation}

Hint:

Let ${\bf e}_i$ be orthonormal unit vectors then in index notation $${\bf u} = u_i {\bf e}_i$$

The dot product between two vectors can then be written

$${\bf a}\cdot {\bf b} = a_ib_i$$

in particular when ${\bf a} = {\bf \nabla}$ we get ${\bf \nabla}\cdot {\bf b} = \partial_ib_i$. The curl can be written

$${\bf a}\times {\bf b} = \epsilon_{kij}a_i b_j {\bf e}_k$$

where $\epsilon_{ijk}$ is the Levi-Civita symbol.

Using this then the first term on the right hand side in your equation becomes

$${\bf u}\times(\nabla\times {\bf u}) = \epsilon_{kij}u_i(\nabla\times {\bf u})_j{\bf e}_k = \epsilon_{kij}\epsilon_{jlm}u_i\partial_lu_m{\bf e}_k$$

Now repeat this for the other terms and compare. You will have to use the identity (the one given by GFR in the comments)

$$\epsilon_{ijk}\epsilon_{imn} = \delta_{jm}\delta_{kn} - \delta_{jn}\delta_{km}$$

to finish it up.