I don't have a definitive answergive an explicit counterexample below, but let me explain why so I believe that the have modified my answer.
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$.