Harald, I certainly will not claim that this is simpler, but there is a spectral approach to your question, which has been considered. Consider the subgroup $BS(1,2)$ of the affine group of the real line, generated by $a:x\mapsto 2x$ (dilation by 2) and $b:x\mapsto x+1$ (translation by 1). If $p$ is an odd prime, reducing modulo $p$ we have a homomorphism $BS(1,2)\rightarrow Aff_1(p)$ (the affine group of $Z/pZ$) and your graphs can be viewed as Schreier graphs of $BS(1,2)$. In that paper
http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.em/1045952352
F. Martin and I prove that the spectrum of the adjacency matrix of the Cayley graph of $BS(1,2)$ w.r.t. $\{a^{\pm 1},b^{\pm 1}\}$is the interval $[-3,4]$, and that it is the closure of the union of the spectra of your graphs. This implies that your graphs cannot have a spectral gap.