I know that every Riemannian metric induces a unique connection.
Question:
My question is if the opposite direction is indeed true. That is given a connection $\nabla$ on $M$ does there exist a Riemannian metric $g_{\nabla}$ on $M$ such that $\nabla$ is the Levi-Civita connection for $g_{\nabla}$?
No, the torsion form of the Levi Civita connection is zero and this is not true for every connection.
See also the answer here for a connection whose torsion form is not zero.
https://mathoverflow.net/questions/133370/torsion-and-non-metricity-tensor-on-a-surface
A torsion free connection is not always a Levi Civita connection. See the answer of Thurston here for examples.
https://mathoverflow.net/questions/54434/when-can-a-connection-induce-a-riemannian-metric-for-which-it-is-the-levi-civita
A characterization of when a metric exits for a given Torsion free metric whose Holonomy group is a subgroup of $O(p,q)$ can be found here: Schmidt