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$.