I'm not sure what happens for general curves, but I think I can prove the following:
Let $\gamma:[0,1]\rightarrow M$ be any injective curve segement. Then there is a Riemannian metric for which $\gamma$ is a geodesic. If instead $\gamma$ is a simple closed curve and $\gamma'(0) = \gamma'(1)$, the conclusion still holds.
I'm not sure what happens in the other cases.
Here's the idea of the proof in the (slightly harder) second case:
Pick a background Riemannian metric once and for all. The normal bundle of $\gamma$ embeds into $M$ via the exponential map (for a suitably short time). Call the image of this embedding $W$. Choose an open set $V$ with the property that $V\subseteq \overline{V}\subseteq W$ and let $U = M-\overline{V}$. Notice that $W\cup U = M$, so we can find partition of unity $\{\lambda_U,\lambda_W\}$ subordinate to $\{U,W\}$.
Now, the classification of vector bundles over circles is easy: There are precisely 2 of any rank - the trivial bundle of rank $k$ and the Möbius bundle + trivial bundle of rank $k-1$. The point is that both of these have (flat) metrics where the $0$ section ($\gamma$) is a geodesic.
Since $W$ is diffeomorphic to a vector bundle over the circle, we can assume it has a metric $g_W$ for which $\gamma$ is a geodesic. Now, pick any Riemannian metric $g_U$ on $U$. Finally, define the metric $g_M$ on $M$ by $\lambda_W g_W + \lambda_U g_U$. This is a convex sum of metrics, and hence is a metric. Near $\gamma$, $\lambda_U \equiv 0$ and $\lambda_W\equiv 1$, so the metric near $\gamma$ looks just like $g_W$, so $\gamma$ is a geodesic in $M$.
Assume that $\gamma :[0,1]\rightarrow M$ is a curve Then
$$
\gamma'(t)= \sum_i\ a_i(t)E_i(t) $$ where $E_i$ is a coordinate
field. Hence $$ \nabla_{\gamma'(t)} \gamma'(t)= \frac{d}{dt} a_i(t)
E_i(t) + a_i(t) a_j(t) \nabla_{E_j} E_i $$
When $f\gamma '=\nabla_{\gamma'(t)} \gamma'(t)$, then $$ fa_i =
\frac{d}{dt} a_i + a_la_m\Gamma_{lm}^i $$
When $a =\gamma\circ h$ has unit speed with $h(s)=t$, then $$ a'(s)=
h'(s) \gamma'(h(s))= h'(s) a_i(h(s)) E_i(a(s)) $$
Hence \begin{align*} \nabla_{a'(s)} a'(s)& =\frac{d}{ds} \{ h' a_i\circ h \} E_i
+h' a_l h' a_m \Gamma_{lm}^i E_i \\& =( h')^2 \{ \frac{d}{dt} a_i + a_la_m \Gamma_{lm}^i \} E_i
\\& =(h')^2 fa_iE_i =C a' \end{align*}
for some function $C$. Since $a'(s)$ is unit speed, then $C=0$
OLD : When $\nabla_{c'}c' =fc'$ and $a=c\circ h$ is unit speed, then $$
a' = h' c',\ \nabla_{a'}a' =\nabla_{h'c'}(h'c')
=h' c'(h') c' +(h')^2 fc' = \underbrace{\{ c' (h') + f
h'\}}_{=F}
a' $$
Note that $0=a'(a',a')=2(\nabla_{a'} a',a')
=2F $ so that $F=0$
Add : We follow the notation in OP :
$\nabla_{\overline{\gamma}'} \overline{\gamma}'= \nabla_{h'\gamma '}
h'\gamma' =h'\gamma'(h')\gamma' + (h')^2 f\gamma' $
Assume that $\nabla_{\overline{\gamma}'} \overline{\gamma}' =0,\
\gamma'\neq 0,\ h'\neq 0 $ Then
$$ \gamma'(t) (h'(s)) + h'f =0 $$
When $t=h(s),\ s=Q(t),\ h\circ Q (t)=t$, then
$$ h'Q'=1,\ h'f=-\frac{d}{dt} h'(s)=-h'' \frac{d}{dt} s=
-h'' \frac{1}{h'} $$
Best Answer
No: consider $(\mathbb{R}^2,\langle\cdot,\cdot\rangle)$ where $\langle\cdot,\cdot\rangle$ is the usual dot product, and $\gamma:\theta\mapsto(\cos(\theta),\sin(\theta))$. Then $||\gamma'(\theta)||^2=1$ but $\gamma$ is not a geodesic of $\mathbb{R}^2$, which are the straight lines.