Can you get them to accept the concept and basic properties of field lines? If you assume that field lines always start and end on charges, and that the flux through a surface is proportional to the number of fields lines that "pierce" it, then Gauss's Law follows.
You might also try a fluid analogy. A positive charge is like the end of a hose with water flowing out of it, and a negative charge is like a drain hole where water flows in. The flux through a surface is the number of gallons (or liters) per second.