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