It seems likely to me that the (graphs of) Hecke operators on the self-product of a modular curve have this property. This might be a little hard to verify because of the cusps, so it is better to work with suitable Shimura curves (quotients of the upper half plane by a torsion free arithmetic subgroup of an indefinite rational quaternion algebra). 

In the case of Shimura curves one gets a curve C of genus > 1 (lots of them in fact) and infinitely many curves Gamma_i in C \times C such that both projection maps from Gamma_i to C are finite and etale. This shows that the self intersection of each Gamma_i is negative. The degrees of these maps go to infinity, hence so does the genus of the Gamma_i.

(In the case of the usual modular curves the projection maps are not etale which is what makes the computation of the self-intersection more difficult.)

THIS DOESN'T WORK! (Sorry.)

The problem is that even though we get curves Gamma_i with two (distinct) etale maps to C (a Shimura curve, say) the image in C x C might be singular, so the self-intersection could well be positive. For the case of modular curves this is in fact the case as may be seen by reducing the mod p. This suggests that the self-intersection numbers are also positive for Shimura curves.