The [restricted isometry property][1], or RIP (formerly known as the uniform uncertainty principle, or UUP, as per your suspicion that uncertainty principles should be relevant) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-4} |G|$; this property was first proven (for $G$ a cyclic group, and with exponent 6 instead of 4) by [Candes and myself][2], and then (for arbitrary abelian $G$, and with exponent 4) by [Rudelson and Vershynin][3].  If one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (of sparsity less than $c |G|/\log^4 |G|$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP, and so the situation described in your post will not occur.

If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group.  But unfortunately this is probably outside of reach of the technology described in the above papers.  (But there has been a number of advances in that area since then, which I have not followed as closely.  For instance, there has been a slight improvement to the Rudelson-Vershynin bound obtained recently [by Cheraghchi, Guruswami, and Velingker][4], although for the problem at hand, it does not appear to lower the exponent $4$ further.)


  [1]: http://en.wikipedia.org/wiki/Restricted_isometry_property
  [2]: http://arxiv.org/abs/math.CA/0410542
  [3]: http://arxiv.org/abs/math/0602559
  [4]: http://arxiv.org/abs/1207.1140