As of Python 3.7, datetime.datetime.fromisoformat() can handle your format:
>>> import datetime
>>> datetime.datetime.fromisoformat('2012-11-01T04:16:13-04:00')
datetime.datetime(2012, 11, 1, 4, 16, 13, tzinfo=datetime.timezone(datetime.timedelta(days=-1, seconds=72000)))
In older Python versions you can't, not without a whole lot of painstaking manual timezone defining.
Python does not include a timezone database, because it would be outdated too quickly. Instead, Python relies on external libraries, which can have a far faster release cycle, to provide properly configured timezones for you.
As a side-effect, this means that timezone parsing also needs to be an external library. If dateutil is too heavy-weight for you, use iso8601 instead, it'll parse your specific format just fine:
>>> import iso8601
>>> iso8601.parse_date('2012-11-01T04:16:13-04:00')
datetime.datetime(2012, 11, 1, 4, 16, 13, tzinfo=<FixedOffset '-04:00'>)
iso8601 is a whopping 4KB small. Compare that tot python-dateutil's 148KB.
As of Python 3.2 Python can handle simple offset-based timezones, and %z will parse -hhmm and +hhmm timezone offsets in a timestamp. That means that for a ISO 8601 timestamp you'd have to remove the : in the timezone:
>>> from datetime import datetime
>>> iso_ts = '2012-11-01T04:16:13-04:00'
>>> datetime.strptime(''.join(iso_ts.rsplit(':', 1)), '%Y-%m-%dT%H:%M:%S%z')
datetime.datetime(2012, 11, 1, 4, 16, 13, tzinfo=datetime.timezone(datetime.timedelta(-1, 72000)))
The lack of proper ISO 8601 parsing is being tracked in Python issue 15873.