Why doesn't string theory have a mass gap? Gravitons are string modes which can have arbitrarily small energies. Just make the wavelength arbitrarily large. String theory has no mass gap, but why? A classical string can only have positive energies. The string tension makes a positive contribution. The string kinetic energy also makes a positive contribution. A classical string can have an arbitrarily small mass because it can be arbitrarily small in length. But quantum strings can't shrink beyond the string scale.
The lack of a mass gap can be traced to a shift factor to the string energy in the Virasoro constraint. For a single string, this shift is unconstrained and arbitrary. Without interactions, this is none other than the "string chemical potential". But we can create/annihilate strings after second quantizing them. This shift becomes physical. Modular invariance of worldsheets of genus one fixes the shift, and it turns out to be negative. String theorists explain this as the Casimir effect on the worldsheet, but this is just a name, and not an explanation. Why is this Casimir shift negative? Only a negative value can cancel the mass gap.
Don't say $ζ$-function regularization, because it's purely formal and doesn't explain a thing.
 A: Dear Iskandar, as we're getting used to, a majority of your question is not a question; it is a sequence of fundamentally incorrect propositions.
The Greek-letter-you-have-prohibited-here-so-I-will-not-write-it function regularization actually explains everything about the issues you're asking. It is a canonical example of an actual calculation that may produce correct values of the string energy - which gets translated to the squared mass of the corresponding particle in spacetime.
With this regularization or any other calculation that is equally valid, one may see that the ground state of the string has a negative energy so the corresponding particle has a negative squared mass. In particular, in bosonic string theory, the ground state of a single string is a tachyon and its mass is
$$ m^2 = -\frac{1}{\alpha'} $$
or its multiples, depending on whether the string is open or closed, and so on. The negative value - the existence of a tachyon - implies that the spacetime of bosonic string theory is unstable and the theory is kind of sick and may only be used as a toy model (at least for closed bosonic strings).
The fact that the ground state world sheet energy - i.e. the squared spacetime mass - has to have this negative value can be showed by various controlled calculations of the single string or, if one decides to deny that the right value may be calculated already for a single string (which it can), the correct shift in the energy is certainly needed for consistent interactions at the one-loop level and beyond. Needless to say, the latter calculations are more demanding than the regularization of the single-string ground state energy but ultimately, the complicated calculations of interactions justify the correct regularizations of the single string, too. (The critical dimension, related to the ground state energy, was first encountered while people calculated one-loop diagrams.)
In the superstring case, the tachyons are projected out of the spectrum but there are always massless particles such as the graviton and indeed, the vanishing of their mass is linked to the existence of a negative-energy state on the world sheet that was removed. At least, this is the case in the RNS formulation of the superstring. In the Green-Schwarz formalism with world sheet fermionic fields that are spacetime spinors, there are no tachyons to start with and the vanishing of the ground state energy directly comes from the cancellation between fermions' and bosons' zero-point energies; you may prefer this formalism if you manage to learn it but the resulting spectrum and interactions are totally equivalent to the RNS formalism. In the Green-Schwarz formalism, the dominant negative contribution is one from the zero-point energy of a fermionic harmonic oscillator that is $-\hbar\omega/2$ much like it's $+\hbar\omega/2$ for the bosonic harmonic oscillators, and those cancel. (There may be other formalisms to formulate a CFT for a given string background, too, and the equivalences may be proved rigorously.)
The value of the ground state energy - the tachyon's squared mass - is negative because we can actually calculate not just the sign but its exact value and this value is negative. The forbidden-Greek-letter function regularization is a transparent way to do it - one that many people, including myself, view as "totally intuitive". But at the end, one has to apply a method to calculate it. One can't scream the right result without doing any calculations.
You should look at the question in the opposite way. Other people may ask you why you think that the ground state energy should be non-negative. And you would answer with some arguments about the positivity of the kinetic and potential energy of a string but these arguments are ultimately wrong when applied to a string which has infinitely many modes. A consistent theory simply can work only when the ground state energy is shifted to the actual level required by consistency - or the world sheet conformal and modular invariance - and the right ground state value is negative. You may imagine that you treat the whole ground state energy as an unknown; you add a possible shift. And at the end, or earlier, you will find out that only for one value of the shift, one may get a consistent theory.
Your last sentence about "formal" arguments betrays your complete misunderstanding of physics as a discipline. Solid answers in physics are all about - and have always been all about, at least from Newton's era - careful mathematical arguments and calculations. To prohibit the people who are supposed to answer your question - or yourself - from using maths is equivalent to make it totally impossible to do any serious physics whatsoever. You can't understand arguments of string theory with no knowledge of maths, or even by denial of the importance and total legitimity of maths. One may cook a soup but he can't do string theory with this lack of pre-requisites. It's simply not possible. String theory - and theoretical physics - is all about maths. 
So in your language, the whole discipline is formal in this sense, and it is how it should be and how it must be. "Informal intuition" may arise by experience but it's clear that one has to work a lot with the maths before he begins to view insights about these theories at the intuitive level. That's simply because for millions of years, our ancestors haven't been trained by evolution to understand the quantum or microscopic world. So it shouldn't be surprising that we encounter lots of things that are not "hard-wired" in our brains and where we really have to rely on very careful, "formal" arguments and calculations rather than primitive emotions. There is no hormone and nothing else in the generic mammals' emotions that can make them instinctively understand why $1+2+3+4+5+\dots = -1/12$ whenever the sum of integers appears in an important calculation. 
Only careful maths may shed light on the identity. One may always "pre-regulate" the theory so that the sum of integers appears in a regulated form, with extra terms that ultimately make it finite, and the right shift is added by hand, and is later adjusted to get an interesting theory. So the $1+2+3+4+5+\dots$ formula may be viewed as a mere "sketch" that misses lots of "bureaucratic" additions, regulators, shifts, and so on. But the ultimate result, in this case and in many others, is completely identical to the result of a calculation that adds no bureaucratic baggage of this kind and that simply sets $1+2+3+\dots$ equal to $-1/12$ whenever it appears. These are aesthetic differences in ways how physicists may calculate various things - they may differ in the way how they think about a problem - but at the end, competent physicists have to agree about the values of all predicted quantities that may be measured.
