Artie, here is a sketch of an argument that I think should work.
Definition (just in case someone needs this): A threefold singularity is called cDV or comopound Du Val or cDV if a general hyperplane section through the singular point has Du Val singularities (a.k.a. rational double point).
Remark Since a rational double point surface singularity is Gorenstein, it follows that so is a cDV singularity. A typical cDV singularity is a one-parameter deformation of a rational double point.
A terminal threefold singularity is a cyclic quotient of an isolated cDV singularity. Say $X'\to X$ is such that $X'$ has cDV singularities. Suppose we already know the statement for cDV singularities. Let $Y''$ denote a resolution of $Y'=X'\times_X Y$. I think $Y'$ should be smooth over a general point of the exceptional locus of $f:Y\to X$, so it should only have isolated singularities, so a general point of the exceptional locus of $f$ is covered by the codimension $2$ part of the exceptional locus of $Y''\to X$. In other words, if we know that that is covered by rational curves, then we are done. (Admittedly I did not work out this part, but it seems reasonable).
Now for the cDV case, it should be easy. A general hyperplane section through the singular point has Du Val singularities, so the exceptional locus over that point can only contain rational curves forming a tree.
I don't know if this is written down anywhere, I just made it up. (So it might not be air-tight).
The same statement for $X$ smooth is known as Abhyankar's lemma and is (1.3) in Kollár-Mori. Interestingly, it is used in the proof of Bend-and-Break (although only for surfaces) which is used in the Cone Theorem, at least the original proof. And I think B&B is actually enough to prove what you want, so you don't need the Cone Theorem, although that is of course also a big gun.
Addendum To answer Artie's question in the comments: The proof of this characterisation of terminal threefold singularities is actually not easy. However, it seems to me that it is not that far from what you want to be proven, so if that can't be proven easily, then probably neither can your statement.
Here are some thoughts to support that pseudo-claim:
1) The cyclic cover part is easy, since one takes the index-one cover, which will be an index-one terminal singularity. I will assume this from this point.
2) A terminal singularity is rational and hence CM, so an index-one terminal singularity is Gorenstein. Therefore any hyperplane section is also Gorenstein.
3) In the situation of the question a general hyperplane section through the singular point may not be resolved by $f$, but if it were, then the exceptional divisor of that resolution would be just the exceptional locus of $f$. That would imply that the exceptional locus of the resolution of the hyperplane section consists of rational curves and since it is equal to the exceptional locus of $f$, if it contained a loop, it would imply that $R^1f_*\mathscr O_Y\neq 0$ (I think I can prove this. It is relatively easy, but not super-easy.) In other words, since $X$ has rational singularities it follows that so does this general hyperplane section. That implies that it has Du Val singularties and hence $X$ has (isolated) cDV.
Conclusion Even if the addendum is not a full proof of the used characterisation of terminal threefold singularities, it seems to suggest that you question is about as hard as that is.