A few thoughts. First you can assume that your group is finitely generated. Second, it does not contain free non-amenable subgroups, free Burnside groups, etc. Moreover, every subgroup of your group also has the same property. Now, you can look at the (not very large) list of known counterexamples to von Neumann's problem (non-amenable groups without free subgroups) to convince yourself that an example of such a group is not known. I strongly suspect that examples do not exist, that is every group satisfying your property must be amenable. I think that the following property may hold for all finitely generated groups: for every infinite finitely generated group $G$ and every $\epsilon\gt 0$ there exists a finite subset $S\subset G$ such that every subset of $S$ containing at least $\epsilon|S|$ elements generates $G$. (By Gromov's thesis this statement, if true, must be trivial.) For example, in the case of $\mathbb Z$, any sufficiently large (of cardinality bigger than $\frac{2}{\epsilon}$) set of primes is such. If it is true, then every group with your property is amenable.

For the free group $F(a,b)$, the set can be constructed as $S=\{a^pb^q, p,q\in I\}$, where $I$ is any set of natural numbers such that for every $x_1\lt x_2 \lt...\lt x_n\in I$ the numbers $x_2-x_1, x_3-x_1,...,x_n-x_1$ are relatively prime (here $n$ depends on $\epsilon$, $|I|$ also depends on $\epsilon$). Indeed, if $I$ is large enough, a subset with $\ge \epsilon|S|$ elements will contain $n$ elements of the form $a^pb^{q_1}, a^pb^{q_2},..., a^pb^{q_n}$ where $q_1\lt q_2\lt...\lt q_n$ are from $I$. Then the subgroup generated by these elements will contain $b$. Similarly it will contain $a$. Instead of the free group, one can take any group $G$ generated by $a,b$ where the set $S$ is infinite. It might be enough to prove my conjecture in general.

** Edit. ** One needs to be more careful in choosing the set $S$ for the free group, but the general idea seems to be correct.