In fact it is not true in this generality: the simple counterexample, inspired by a famous Aesop's fable, is: $X=\mathbb{R}$, $f(x)=x$, and $g(x)=\max(0, 2x-1)$ for $x\in I:=[0,1]$. The Fréchet distance is clearly zero: for $0<\epsilon< 1$ the homeomorphism $ \phi_\epsilon :I\ni x \mapsto \max(\epsilon x, 2x-1)\in I$ gives $\|f\circ \phi_\epsilon-g\|_\infty<\epsilon$. But of course for any homeomorphism $\phi$ from $I$ to itself we have $f\circ\phi=\phi\neq g$, as the former is injective and the latter is not. $$*$$ On the positive side, note that if for continuous $f$ and $g$ from $I$ to $X$ one has $f(I)\neq g(I)$, that is w.l.o.g. $f(t_0)\notin g(I)$ for some $t_0\in I$ , then for any homeomorphism $\phi:I\to I$, $d_\infty(f,g\circ\phi)\ge \min_{t\in I} d_X(f(t_0), g(t))>0$, so that the Fréchet distance $\tilde d(f,g)$ is non-zero.
Therefore, if $f$ and $g$ are injective and have zero Fréchet distance, then they are both homeomorphisms with the compact $f(I)=g(I)$ so $\phi:=f^{-1}\circ g$ is a homeomorphism $I\to I$ such that $g=f\circ\phi$. (rmk: At this point one also sees that $\phi:I\to I$ is increasing, because a decreasing homeomorphism would always give a positive Fréchet distance between $f$ and $f\circ\phi$, for any non-constant curve $f$).
(Nothing changes if we replace $I$ with a compact space $K$, where in the definition of the analogous Fréchet distance the quotient is over all homeomorphisms $K\to K$.)