I tried to create a new template. I followed a non-existing URL: https://developer-new.mozilla.org/en-US/docs/Template:NotExistingTest and I was expecting to be able to create the page, but I get a 404. (I was trying to create Template:CustomCSS)
It's possible you didn't have template editing permissions; I added them, see if it works now.
I can't create new templates all of a sudden anyway, it seems.
You can't create a template that way. In fact, you can't create any page that way. There's a "new template" link here that should work for creating templates: https://developer-new.mozilla.org/en-US/docs/ The link in particular is: https://developer-new.mozilla.org/en-US/docs/new?slug=Template: We had bug 760240 to create pages on 404, but that only works for subpages of existing sections. The 404 for Template:NotExistingTest is because no template is a part of an existing parent section. If we want to change how that works, though, reopen bug 760240 and comment. Also, if the template creation link in this comment doesn't work, reopen this one.