Re: "%z format is supported".

That's platform-specific; the actual parsing is delegated to the C library.  It's not in Python 2.7 / Win32:

  ValueError: 'z' is a bad directive in format '%Y-%m-%dT%H:%M:%S%z'

It really shouldn't be platform-specific; the underlying platform is irrelevant to this task.  That's more of a documentation error; the features not common to all supported Python platforms should not be mentioned in the documentation.  

Re: "I would very much like such promiscuous parser to be implemented in datetime.__new__. "

For string input, it's probably better to do this conversion in a specific class-level function.  Full ISO 8601 dates/times generally come from computer-generated data via a file or API.  If invalid text shows up, it should be detected as an error, not be heuristically interpreted as a date.  There's already "fromtimestamp" and "fromordinal", 
and "isoformat" as an instance method, so "fromisoformat" seems reasonable.

I'd also suggest providing a standard subclass of tzinfo in datetime for fixed offsets.  That's needed to express the time zone information in an ISO 8601 date. The new "fromisoformat" would convert an ISO 8601 date/time would be convertible to a time-zone "aware" datetime object.  If converted back to an ISO 8601 string with .isoformat(), the round trip should preserve the original data, including time zone offset.

(Several more implementations of this conversion have turned up.  In addition to the four already mentioned, there was one in xml.util, and one in feedparser. There are probably more yet to be found.)