For the sake of completeness, here is the local story, assuming that geodesics are understood as maps from intervals to the manifold and "the same" is understood literally (rather than "up to reparameterization"). Equivalently, two metrics have the same exponential map.
Results along these lines are well-know but hard to find (with usual references pointing to old papers by Eisenhart which I find unreadable), while this should be standard textbook material...
I will say that two Riemannian metrics with the same Levi-Civita connection form an LC pair. I will say that an LC pair is trivial if the metrics are homothetic to each other, i.e. are scalar multiples of each other.
The first thing to observe is that two Riemannian metrics on the given manifold have the same exponential map if and only if they form an LC pair. One direction is immediate, as geodesics on a Riemannian manifold are curves defined by the differential equation $\nabla_{c'} c'=0$. The opposite direction is harder, it is proven (for instance) in:
M.Spivak, "Comprehensive Introduction to Differential Geometry" (Publish Or Perish, 2000), volume 2, chapter 6, Appendix 1.
Theorem. Suppose that $(M,g_1)$ is a Riemannian manifold such that $M$ admits another Riemannian metric $g_2$ such that $g_1, g_2$ form a nontrivial LC pair. Then $(M,g_1)$ is locally isometric to a product of Riemannian manifolds.
Proof. I will need several ingredients. Recall that the holonomy group $Hol_{p,g}$ of the Riemannian metric $g$ (rel. basepoint $p\in M$) depends only on the Riemannian affine connection $\nabla$, $Hol_{p,g}=Hol_{p,\nabla}$. Our discussion is local, it suffices to restrict to loops contained in a totally convex neighborhood of $p$. Since $\nabla$ is a Riemannian connection (for a metric $g$) then $G=Hol_{p,\nabla}$ will preserve the quadratic form $g_p$ on $T_pM$. Thus, $G$ is a relatively compact subgroup of $O(n)=Aut(T_pM, g_p)$. This group is essentially independent of the basepoint: Holonomy groups at different base-points $p_1, p_2$ in $M$ are "conjugate" via the parallel transport along a path from $p_1$ to $p_2$.
Next, comes a fact from elementary representation theory. Suppose that $V$ is a finite-dimensional real vector space and $G< GL(V)$ is a (relatively) compact subgroup whose action on $V$ is irreducible, i.e. $V$ does not admit a nontrivial $G$-invariant direct sum decomposition $V=V_1\oplus V_2$. Then any two $G$-invariant quadratic forms $q_1, q_2$ on $V$, are scalar multiples of each other.
Applying this result to the holonomy groups of Riemannian metrics $g_1, g_2$ on a connected manifold $M$ we obtain:
If $g_1, g_2$ have the same Levi-Civita connection $\nabla$ then either the holonomy groups $Hol_{p,\nabla}$ are reducible for some (equivalently, every) $p\in M$ or the metrics $g_1, g_2$ are conformal to each other: $$ g_2= e^{2f}g_1, f\in C^\infty(M). $$
Another ingredient that we need is deRham's theorem:
If $g$ is a Riemannian metric on $M$ whose holonomy is reducible, then $M$ locally splits as a Riemannian direct product.
See e.g. Theorem 3.1 on p. 228 in Petersen's book "Riemannian Geometry."
Applying this to an LC pair $g_1, g_2$, we conclude:
Either (1) $(M,g_1)$ locally splits as a Riemannian direct product or (2) the metrics $g_1, g_2$ are conformal to each other.
Consider the case (2):
$$
g_2= e^{2f}g_1, f\in C^\infty(M).
$$
I will prove that the function $f$ is constant, i.e. $g_1, g_2$ form a trivial LC pair. Let $grad(f)$ denote the gradient field of $f$ with respect to $g_1$. Then, since $g_1, g_2$ form an LC pair, one obtains:
$$
X(f)Y + Y(f)X - g_1(X,Y) grad(f)=0,
$$
for any two vector fields $X, Y$ on $M$. I claim that $grad(f)$ is identically zero on $M$, i.e. $f$ is constant.
Indeed, consider vector fields $X=Y= grad(f)$. Then, the equation becomes
$$
2 ||grad(f)||^2 grad(f) - ||grad(f)||^2 grad(f) = ||grad(f)||^2 grad(f)=0,
$$
i.e. $grad(f)$ is identically zero. Thus, the metric $g_2$ is a constant multiple of $g_1$. qed
Clearly, the "converse" to this theorem holds as well assuming that $(M,g_1)$ has a global nontrivial deRham decomposition.
Applying the theorem inductively, one obtains the following corollary:
Corollary. Let $(M,g)$ be a Riemannian manifold which has local deRham decomposition $$ M=M_0\times M_1\times ... \times M_m, g= g_0 \oplus g_1\oplus ... \oplus g_m $$ where $g_0=\delta_{ij}$ is the standard flat metric on ${\mathbb R}^k$ (and the rest of the factors are non-flat and do not split any further). Suppose that $g, h$ is an LC pair on $M$. Then (locally) $h$ has the form $$ h= h_0 \oplus a_1 g_1\oplus ... \oplus a_m g_m $$ where $h_0$ is a constant metric tensor on ${\mathbb R}^k$ and $a_1,...,a_m$ are certain constants.