If $\nabla$ is any connection and $f$ a function, its Hessian with respect to $\nabla$ is $\mathrm{Hess}^{\nabla}f = \nabla \mathrm{d}f$, and one can see, after a messy calculation, that:
$$
\mathrm{Hess}^{\nabla}f(X,Y) - \mathrm{Hess}^{\nabla}f(Y,X) = \pm\mathrm{d}f\left([X,Y] - (\nabla_XY - \nabla_YX) \right)
$$
(where the $\pm$ sign is here because I don't remember the exact sign, but the computations are not that hard, just messy.) Hence, Hessians are symmetric if and only if the connection is torsion-free. This is the main motivation to consider torsion-free connections: in the euclidean space, Hessians are symmetric!
Moreover, the fundamental theorem of Riemannian geometry tells us that on a Riemannian manifold, there is a unique connexion that is torsion-free and lets the metric invariant, that is:
$$
\forall X,Y,Z, \left(\nabla_Zg\right)(X,Y) = Z\cdot g\left(X,Y \right) - g\left(\nabla_ZX,Y\right) - g\left(X,\nabla_ZY\right) = 0.
$$
(compare with the euclidean case, where $\langle X,Y\rangle ' = \langle X',Y\rangle + \langle X, Y' \rangle$.)
This theorem thus says that given any Riemannian metric $g$, there is a connection that is better than others: Hessians are symmetric and the metric is invariant under the action. We call it the Levi-Civita connexion.
If a connection is chosen, a geodesic is a parametrized curve satisfying the equation of geodesics : $\nabla_{\gamma'}\gamma' = 0$. Thus a curve $\gamma$ is a geodesic with respect to the connection, and can be a geodesic for some connection $\nabla^1$ but not for another connecion $\nabla^2$. Therefore, your question does not really have sense: we do not say that a connexion gives the least energy of a geodesic. I think you got confused, believing that being a geodesic is an intrinsic notion, but it really depends on the connection you consider.
Now, suppose $(M,g)$ is a Riemannian manifold endowed with its Levi-Civita connexion. Then if $\gamma : [a,b] \to M$ is a curve, we define its energy to be:
$$
E(\gamma) = \frac{1}{2}\int_a^b \|\gamma'\|^2
$$
and one can show that, in the space of all curves $\{\gamma : [a,b] \to M\}$ with same end points, a curve $\gamma$ is a point where the energy functional is extremal if and only if $\nabla_{\gamma'}\gamma'=0$, that is if and only if $\gamma$ is a solution of the equation of geodesics. Hence, a minimizer of the energy functional is a geodesic.
Short answer to your question is Yes. The way to do it is by "stealing the algebraic formula of Leibniz rule". Let's begin by recalling the "Tensor Characterization Lemma".
Tensor characterization Lemma: Let $M$ be a manifold, let $F:\chi(M)^k\rightarrow C^{\infty}(M)$ be a $C^{\infty}(M)$ multilinear map. Then there exists a unique smooth $(k,0)$ tensor field $w$ such that for every $X_1,X_2,...,X_k \in C^{\infty}(M)$ and every $p\in M$ we have that $F(X_1,X_2,..,X_k)|_p=w|_p(X_1(p),X_2(p),...,X_k(p))$.
The above lemma allows us to naturally identify smooth tensor fields with $C^{\infty}(M)$ multilinear map. This is a convineant algebraic point of view. Once we are done with this identification, we just need to define $C^{\infty}(M)$ multilinear map $\nabla_YF$ in $k$ arguments for any $C^{\infty}(M)$ multilinear map $F$ in $k$ arguments and any vector field $Y$ as below:
$$(\nabla_YF)(X_1,X_2,...,X_k)= Y(F(X_1,X_2,...,X_k))-\sum_{i=1}^k F( (\nabla_Y)^i(X_1,X_2,...,X_k)) $$
Where $X_1,X_2,...,X_k$ are arbitrary vector fields and $(\nabla_Y)^i(X_1,X_2,...,X_k)$ means apply the operator $\nabla_Y$ to $X_i$.
One checks easily that $\nabla_YF$ will be indeed $C^{\infty}(M)$ multilinear map in $k$ arguments.
The above was an algebraic approach, here is an alternative geometric approach:
Let $w$ be smooth $(k,0)$ Tensor field and let $(p,v)\in TM$, then we define the multilinear map $\nabla_{(p,v)}w:(T_pM)^k\rightarrow \mathbb{R}$ as follows:
Let $\gamma$ be any smooth path such that $\gamma'(0)=(p,v)$, then for any tangents $u_1,u_2,...,u_k$ at $p$ we define $\nabla_{(p,v)}w(u_1,u_2,...,u_k)$ to be $\frac{d}{dt}|_0(w|_{\gamma(t)}(P^t(u_1),P^t(u_2),...,P^t(u_k))$, where $P^t:T_pM\rightarrow T_{\gamma(t)}M$ is the parallel transport map along $\gamma$. It turns out that this definition is independent of the choice of the smooth path $\gamma$ and so is a valid way to define $\nabla_{(p,v)}w$
Best Answer
This is something I have been thinking about recently, allow me to complete Mariano Suárez-Alvarez' answer.
First just an observation: "pick any Riemannian manifold with trivial holonomy at each point: for example, a space form of curvature zero": actually you have no choice, a connection with trivial holonomy has vanishing curvature, so the only candidate metrics are Euclidean. In the language of geometric structures, a flat torsion-free connection is equivalent to an affine structure.
Now to the point. As we are going to see, the answer to your question is "generically, yes". First note that given a connection $\nabla$ (let's permanently assume that $\nabla$ is torsion-free otherwise there's no chance of it being a Riemanniann connection), by definition a metric $g$ has Levi-Civita connection $\nabla$ if and only if $g$ is $\nabla$-parallel: $\nabla g = 0$.
Let us make a general observation about parallel tensor fields with respect to a given connection. If $F$ is a parallel tensor field, then $F$ is preserved by parallel transport. In particular:
Conversely, given a tensor $F_{x_0}$ in some tangent space $T_{x_0} M$ such that $F_{x_0}$ is invariant under $\operatorname{Hol}(\nabla, x_0)$, there is a unique parallel tensor field $F$ on $M$ extending $F_{x_0}$ (obtained by parallel-transporting $F_{x_0}$).
So you have the answer to your question in the following form:
Now you may want to push the analysis further: how many is that? The answer is provided by analysing the action of the restricted holonomy group $\operatorname{Hol}_0(\nabla, x_0)$ on $T_{x_0}M$. Now this is just linear algebra: let's just call $G = \operatorname{Hol}_0(\nabla, x_0)$ and $V = T_{x_0} M$. Let $g$ and $h$ be two inner products in $V$ that are preserved by $G$, in other words $G \subset O(g)$ and $G \subset O(h)$. If $G$ acts irreducibly on $V$, i.e. there are no $G$-stable subspaces $\{0\} \subsetneq W \subsetneq V$, then a little exercise that I am leaving to you shows that $g$ and $h$ must be proportional. So in the generic case where $\nabla$ is irreducible, the answer to your question is yes:
NB: note that there might not be any such metrics if $G$ does not preserve any inner product on $V$, in other words $G$ must be conjugated to a subgroup of $O(n)$.
On the opposite side of the spectrum, if $G$ is trivial, i.e. $\nabla$ is flat, then $g$ and $h$ can be anything, there are no restrictions:
In the "general" case where $\nabla$ is reducible, I hope I am not mistaken (I won't write the details) in saying that you can derive from the de Rham decomposition theorem that the situation is a mix of the two previous "extreme" cases:
If this is correct, I believe your question is answered completely.
NB: In this paper (see also this one), Richard Atkins addresses this question. I haven't really looked but since it seems to me that there is not much more to say than what I've written, I have no idea what he's really doing in there.