Theorem:
Let $(M,g)$ be a Riemannian Manifold. Then there exists a unique Riemannian connection on $M$.
My concern is with the existence part. In particular, I am unsure as to why the following holds:
Let $X,Y$ and $Z$ be smooth vector fields on $M$ Define $\nabla_{X}Y$ by
\begin{align} \langle \nabla_{X}Y,Z\rangle &= \frac{1}{2}(X\langle Y,Z\rangle +Y\langle Z,X\rangle -Z\langle X,Y\rangle \\ &\ \ \ -\langle X,[Y,Z]\rangle +\langle Y,[Z,X]\rangle +\langle Z,[X,Y]\rangle ). \end{align} This defines a connection on $M$. Why does this define $\nabla_{X}Y?$ and how do I show that $\nabla_{X}Y$ is a smooth vector field? Please do not use Christoffel symbols.
The actual verification is perhaps annoying but straightforward (people already linked other answers in the comments). But here's a few further comments about the truth behind the Koszul formula:
to define $\nabla$, you need to define $\nabla Y$ for all $Y$, where $(\nabla Y)(X) = \nabla_XY$.
since the metric is non-degenerate, knowing $\nabla_XY$ is the same as knowing $\langle \nabla_XY,\cdot\rangle$. That is, the same as knowing $\langle \nabla_XY,Z\rangle$ for all $Z$. This is exactly what the Koszul formula does.
If we write $Y_\flat = \langle Y,\cdot\rangle$, the Koszul formula may be rewritten as $$2\langle \nabla_XY,Z\rangle = (\mathcal{L}_Yg)(X,Z) + {\rm d}(Y_\flat)(X,Z),$$where $g$ is the metric, $\mathcal{L}$ denotes Lie derivative and ${\rm d}$ is the exterior derivative. Since $\nabla$ will satisfy a Leibniz rule, the above formula makes sense: we have a derivation term $\mathcal{L}_Yg$ and a linear (in $Y$) term ${\rm d}(Y_\flat)$, which should be thought of as the curl of $Y$.
Also, smoothness of $\nabla_XY$ follows from everything else in the Koszul formula being smooth (although smoothness can be shown easier with local computations using Christoffel symbols).