The answer is no. The paper Generic free subgroups and statistical hyperbolicity, by Suzhen Han and Wen-yuan Yang, proves almost virtually free for a class of groups which includes relatively hyperbolic groups.

To make sure we are on the same page I will state the result precisely in the case of relatively hyperbolic groups. Define $U^{(k)}:=\{(u_1,...,u_k) \mid u_i \in U\}$. Let $G$ be a relatively hyperbolic group generated by a finite set $S$ and let $B_n$ be the ball of radius $n$ in the Cayley graph of $(G,S)$ centered at the identity. They show

$$\lim_{n \to \infty} \frac{ \left|X \cap B_n^{(k)}\right|}{|B_n^{(k)}|} = 1$$

where $X \subseteq G^{(k)}$ is the set of elements $(g_1,...,g_k)$ such that $\langle g_1,...,g_k \rangle $ is a free group of rank $k$ (Corollary of Corollary 1.6). In particular:

  • Almost virtually free does not imply hyperbolicity since relatively hyperbolic does not imply hyperbolic (see next bullet point for an example).
  • Almost virtually free groups can have subgroups which are not almost virtually free. Note that $\mathbb{Z}^2$ is not almost virtually free but can be contained in relatively hyperbolic groups. If $M$ is a finite volume hyperbolic three manifold with cusps then $\pi_1(M)$ is relatively hyperbolic and contains $\mathbb{Z}^2$ subgroups.

I would like to point out that what is shown in Exponentially generic subsets of groups is somewhat different from the result above for hyperbolic groups. Essentially what they prove is that when you look at surjective homomorphism $F(S) \to G$, $G$ hyperbolic, that tuples of words generically map to tuples of elements which generate a free group. This is somewhat different from the ball model of randomness and I don't believe it follows that you get the almost virtually free property for hyperbolic groups.

If instead you use this model of randomness then your question still has a negative answer. The authors of this paper point out groups which have surjective homomorphisms to non-elementary hyperbolic groups have the "word almost virtually free property". For example you get that $F_n \times \mathbb Z$ has this property, witnessed by the projection to $F_n$.