4 Added a remark that characterizes the solutions

Such functions don't always exist: Suppose you take an oriented surface $\mathcal{M}\subset\mathbb{E}^3$, maybe, say, an embedded torus such that it has no umbilics and such that at least one family of its principal curves (i.e., the lines of curvature) wind densely around the torus, suppose further . It then turns out that, for $|t|<\epsilon$, the oriented-distance $t$ parallel surface $\mathcal{M}_t$ (where $\mathcal{M} = \mathcal{M}_0$) also has these properties. An example is constructed below. [Note that the standard ellipsoid is very different: The lines of curvature on an ellipsoid are all closed. However, this is very unusual behavior. Most differential geometry books give the ellipsoid example because it's pretty and computable, and this tends to make students think that lines of curvature are 'usually' closed, but they are not.]

One further remark: It turns out that a necessary and sufficient condition for the existence of a non-trival solution $(f_2,f_3)$ for the given $f_1$ is simply this: A nontrivial (in the OP's sense) solution exists if and only if there exist functions $g_2$ and $g_3$ on $\mathcal{M}$ with the properties that $dg_2\wedge dg_3$ is nonvanishing on a dense open set in $\mathcal{M}$ and that each $g_i$ is constant on a family of principal curves on $\mathcal{M}$. Sufficiency follows since one can simply take $f_i = \pi^*(g_i)$ for $i=2$ or $3$ where $\pi:\mathcal{S}\to\mathcal{M}$ is the retraction of the shell $\mathcal{S}$ to $\mathcal{M}$ long the normal lines from $\mathcal{M}$. Necessity follows since, if $f_2$ and $f_3$ exist, then one can simply define $g_i$ to be the restriction of $f_i$ to $\mathcal{M}$. Thus, one can see that the behavior of the principal curves on $\mathcal{M}$ completely determines whether or not there are solutions.

3 added 248 characters in body

I give an explicit counterexample below, so I have modified my answer.: No, they these sorts of orthogonal coordinates on 'shells' of parallel compact surfaces don't always (or even usually) exist, and here is the basic . The reason has to do with whether there are nonconstant functions on the given surface $\mathcal{M}$ that are constant on one of the families of principal curves.

Such functions don't always exist: Suppose you take an oriented surface $\mathcal{M}\subset\mathbb{E}^3$, maybe, say, an embedded torus such that it has no umbilics and such that at least one family of its principal curves (i.e., the lines of curvature) wind densely around the torus, suppose further that, for $|t|<\epsilon$, the oriented-distance $t$ parallel surface $\mathcal{M}_t$ (where $\mathcal{M} = \mathcal{M}_0$) also has these properties. An example is constructed below. [Note that the standard ellipsoid is very different: The lines of curvature on an ellipsoid are all closed. However, this is very unusual behavior. Most differential geometry books give the ellipsoid example because it's pretty and computable, and this tends to make students think that lines of curvature are 'usually' closed, but they are not.]

I claim that, for a surface as above, the desired functions $f_2$ and $f_3$ will not exist on the $\epsilon$-shell $\mathcal{S}$ around $\mathcal{M}$. The reason is that each noncritical level set of $f_2=c$ (for example) will be closed in $\mathcal{S}$ and will have to intersect each $\mathcal{M}_t$ in a line of curvature, which, by supposition, is a dense curve in $\mathcal{M}_t$. Thus, this (closed) level set will have to include $\mathcal{M}_t$. Hence, this level set must be a disjoint union of the parallel surfaces $\mathcal{M}_t$. It follows that $\nabla f_1$ and $\nabla f_2$ must be parallel along any noncritical level set of $f_2$. However, this is absurd, because $\nabla f_1$ and $\nabla f_2$ must be perpendicular wherever $\nabla f_2$ is nonvanishing and $\nabla f_2$ does not vanish along a noncritical level set (by definition). It follows, then that $f_2$ cannot have any noncritical level sets, i.e., $\nabla f_2$ must vanish identically. Since you don't consider this to be a nontrivial solution, there are no nontrivial solutions.

Added comment (an explicit example): It turns out that there's an easy explicit example of a torus for which there is no nontrivial solution. Let $C\subset\mathbb{E}^3$ be a closed, embedded, regular space curve, parametrized by arclength $ds$. Thus, associated to the inclusion mapping $X:C\to\mathbb{E}^3$, there will be its Frenet apparatus, i.e., an orthonormal frame field $T,N,B:C\to S^2$ and functions $\kappa,\tau:C\to\mathbb{R}$ with $\kappa >0$ such that $$dX = T\ ds,\quad dT = \kappa N\ ds,\quad dN = (\tau B -\kappa T)\ ds,\quad dB = -\tau N\ ds.$$ It is easy to see that there are such curves with $\int_C \tau\ ds$ being an irrational multiple of $\pi$, so let's assume this. Now, for sufficiently small $t>0$, consider the tube of radius $t$ about $C$, parametrized by $Y:C\times Y_t:C\times S^1\to\mathbb{E}^3$ where $$Y_t = X + t\cos\theta\ N + t\sin\theta\ B.$$ (We require only that $t$ be so small that $Y_t$ be a smooth embedding of $C\times S^1$. In particular, we want $t$ to be less than $1/\kappa_{max}$.) This is a parallel family of surfaces.

It is easy to compute that the principal curves on $Y_t$ are the leaves of the two foliations $ds=0$ and $d\theta + \tau(s)\ ds = 0$. Because I required that $\int_C\tau\ ds$ be an irrational multiple of $\pi$, it follows that each of the leaves of $d\theta + \tau(s)\ ds = 0$ is dense in $C\times S^1$. Consequently, the above argument applies to show that, even though you can take $f_1$ to be $t$ for this family, and, say $f_3$ to be some function of $s$, any function $f_2$ on a shell constructed by taking $t$ in some small interval in $(0,1/\kappa_{max})$ that satisfies $d f_2 \wedge(d\theta + \tau(s)\ ds) =0$ will have to be constant on the level sets of $f_1$.

No, they don't always (or even usually) exist, and here is probably 'no': the basic reason: Suppose you take an oriented surface $\mathcal{M}\subset\mathbb{E}^3$, maybe, say, an embedded torus such that it has no umbilics and such that at least one family of its principal curves (i.e., the lines of curvature) wind densely around the torus, suppose further that, for $|t|<\epsilon$, the oriented-distance $t$ parallel surface $\mathcal{M}_t$ (where $\mathcal{M} = \mathcal{M}_0$) also has these properties. (It's not hard to believe that there exists such a torus, in fact, it seems likely that a 'generic' umbilic-free embedding of the torus, or at least an open set of such, would have this propertyAn example is constructed below. Explicitly constructing such a surface might not be easy, though.) [Note that the standard ellipsoid is very different: The lines of curvature on an ellipsoid are all closed. However, this is very unusual behavior. Most differential geometry books give the ellipsoid example because it's pretty and computable, and this tends to make students think that lines of curvature are 'usually' closed, but they are not.]
I claim that, for a surface as above, the desired functions $f_2$ and $f_3$ will not exist on the $\epsilon$-shell $\mathcal{S}$ around $\mathcal{M}$. The reason is that each noncritical level set of $f_2=c$ (for example) will be closed in $\mathcal{S}$ and will have to intersect each $\mathcal{M}_t$ in a line of curvature, which, by supposition, is a dense curve in $\mathcal{M}_t$. Thus, this (closed) level set will have to include $\mathcal{M}_t$. Hence, this level set must be a disjoint union of the parallel surfaces $\mathcal{M}_t$. It follows that $\nabla f_1$ and $\nabla f_2$ must be parallel along any noncritical level set of $f_2$. However, this is absurd, because $\nabla f_1$ and $\nabla f_2$ must be perpendicular wherever $\nabla f_2$ is nonvanishing and $\nabla f_2$ does not vanish along a noncritical level set (by definition). It follows, then that $f_2$ cannot have any noncritical level sets, i.e., $\nabla f_2$ must vanish identically. Since you don't consider this to be a nontrivial solution, there are no nontrivial solutions.
Added comment (an explicit example): It turns out that there's an easy explicit example of a torus for which there is no nontrivial solution. Let $C\subset\mathbb{E}^3$ be a closed, embedded, regular space curve, parametrized by arclength $ds$. Thus, associated to the inclusion mapping $X:C\to\mathbb{E}^3$, there will be its Frenet apparatus, i.e., an orthonormal frame field $T,N,B:C\to S^2$ and functions $\kappa,\tau:C\to\mathbb{R}$ with $\kappa >0$ such that dX = T\ ds,\quad dT = \kappa N\ ds,\quad dN = (\tau B -\kappa T)\ ds,\quaddB = -\tau N\ ds.It is easy to see that there are such curves with $\int_C \tau\ ds$ being an irrational multiple of $\pi$, so let's assume this. Now, for sufficiently small $t>0$, consider the tube of radius $t$ about $C$, parametrized by $Y:C\times S^1\to\mathbb{E}^3$ where Y_t = X + t\cos\theta\ N + t\sin\theta\ B.(We require only that $t$ be so small that $Y_t$ be a smooth embedding of $C\times S^1$. In particular, we want $t$ to be less than $1/\kappa_{max}$.) This is a parallel family of surfaces.
It is easy to compute that the principal curves on $Y_t$ are the leaves of the two foliations $ds=0$ and $d\theta + \tau(s)\ ds = 0$. Because I required that $\int_C\tau\ ds$ be an irrational multiple of $\pi$, it follows that each of the leaves of $d\theta + \tau(s)\ ds = 0$ is dense in $C\times S^1$. Consequently, the above argument applies to show that, even though you can take $f_1$ to be $t$ for this family, and, say $f_3$ to be some function of $s$, any function $f_2$ on a shell constructed by taking $t$ in some small interval in $(0,1/\kappa_{max})$ that satisfies $d f_2 \wedge(d\theta + \tau(s)\ ds) =0$ will have to be constant on the level sets of $f_1$.