I'm not an expert on this so bare with me, but I don't think you must require $\dim(M) = 26$, you must only require that the worldsheet is conformally invariant - i.e., the Weyl anomaly vanishes. You can do this by adding 26 bosons (which represent the coordinates of $M$) - which is called critical string theory - or you can turn on the dilaton expectation value - which is then called non-critical string theory. There's a lot of interesting research involving these non-critical string theories, for e.g. check out $c=1$ matrix models and type 0 string theories.