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 couple of homeomorphisms $\phi$ and $\psi$ from $I$ to itself  we have $f\circ\phi\neq g\circ\psi$, 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$.