Can every curve on a Riemannian manifold be interpreted as a geodesic of a given metric?

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

I expect that if $M$ is a (connected!) differentiable manifold and $\gamma_1, \gamma_2: S^1 \rightarrow M$ are any two smooth embeddings, there is a diffeomorphism $\Phi: M \rightarrow M$ such that $\gamma_2 = \Phi \circ \gamma_1$. If so, this gives a positive answer to your question restricted to smoothly embedded loops. And something similar should work for smooth embeddings of $\mathbb{R}$ with closed image.

Added: The above is certainly not generally valid: I seem to have forgotten about the fundamental group. It seems like it might still have a chance to hold in the simply connected case. (Also, in the case of surfaces, if you take a metric of constant curvature, I seem to recall that every homotopy class has a unique geodesic representative, so this obstruction is not a problem at least in that case.)

As for the second question: of course there are going to be many Riemannian metrics than geodesic curves: changing the metric in an open set bounded away from the geodesic will certainly not disturb that curve's being a geodesic. As for changes of metric which preserve all geodesic curves rather than just a given one, that's a more interesting question, but at least you can uniformly rescale the metric without affecting any of the geodesics.

$$ \text{These are the geodesics: $\gamma_{a,b}$.} $$

Let $M$ be normed-space with norm $||\cdot||$.

Fix $\gamma:[0,1]\times M \times M \to M$ continuous in the norm topology. Let $\gamma_{a,b}: [0,1] \to M$ be defined by $\gamma_{a,b}=\gamma(a,b,\cdot)$.

Define $$ l_{a,b}(\Gamma) = \int_0^1 |\Gamma(t) - \gamma_{a,b}(t)|\, dt + \int_0^1 |\gamma_{a,b}(t)|\, dt,\\ \text{where } \Gamma \in C_{a,b} = [\text{Continuous } \Gamma:[0,1]\to M \text{ such that } \Gamma(0) = a, \Gamma(1) = b] \quad(a,b\in M). $$

Define $$ d(a,b) = \inf_{\Gamma \in C_{a,b}} l_{a,b}(\Gamma) \quad (a,b \in M). $$

Define $$ \text{len}(\Gamma) = \inf_{P \sqsubset [0,1]} \sum d(\Gamma(x_{n+1}),\Gamma(x_{n})) \quad (\Gamma\in C). \quad (\text{This is Just notation.}) $$

$$ \text{These are the geodesics: $\gamma_{a,b}$.} $$

Remark. $l_{a,b}(\Gamma)$ is not the length of $\Gamma$. The definition of $\text{len}(\Gamma)$ includes a term account for the distance between $x_{n}$ and $x_{n+1}$. As stated, the right side is Just notation.

Extreme Competence Assumed.