Is it possible to write down a Lagrangian for a string theory with a critical dimension different than the familiar 10 or 26? How could one find a string theory Lagrangian for a given dimension? Could you prove that no string theory exists for a given critical dimension?
You write a lagrangian for a string propogating in $(d,1)$ dimensional spacetime and notice that it is equivalently a 2d conformal field theory on the worldsheet of the string. Consistency conditions (vanishing of the conformal anomaly) then imply that necessary dimension of spacetime be 26 for bosonic string theory and 10 for superstring theory.
I wouldn't go as far as to say that string theory cannot exist in any other dimension. The conservative statement to make would be that so far, we only know how to make it work sensibly in the specific cases mentioned above and from what we understand today, seems like it won't work in other dimensions.