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 versions before version 3.9 do not include a timezone database, because it would be outdated too quickly. Instead, for those versions Python relied 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 was being tracked in Python issue 15873 (since migrated to GitHub issue #60077).

I have found that the best approach is to convert the "moment" of interest to a utc-timezone-aware datetime object (in python, the timezone component is not required for datetime objects).

Then you can use astimezone to convert to the timezone of interest (reference).

from datetime import datetime
import pytz

utcmoment_naive = datetime.utcnow()
utcmoment = utcmoment_naive.replace(tzinfo=pytz.utc)

# print "utcmoment_naive: {0}".format(utcmoment_naive) # python 2
print("utcmoment_naive: {0}".format(utcmoment_naive))
print("utcmoment:       {0}".format(utcmoment))

localFormat = "%Y-%m-%d %H:%M:%S"

timezones = ['America/Los_Angeles', 'Europe/Madrid', 'America/Puerto_Rico']

for tz in timezones:
    localDatetime = utcmoment.astimezone(pytz.timezone(tz))
    print(localDatetime.strftime(localFormat))

# utcmoment_naive: 2017-05-11 17:43:30.802644
# utcmoment:       2017-05-11 17:43:30.802644+00:00
# 2017-05-11 10:43:30
# 2017-05-11 19:43:30
# 2017-05-11 13:43:30

So, with the moment of interest in the local timezone (a time that exists), you convert it to utc like this (reference).

localmoment_naive = datetime.strptime('2013-09-06 14:05:10', localFormat)

localtimezone = pytz.timezone('Australia/Adelaide')

try:
    localmoment = localtimezone.localize(localmoment_naive, is_dst=None)
    print("Time exists")

    utcmoment = localmoment.astimezone(pytz.utc)

except pytz.exceptions.NonExistentTimeError as e:
    print("NonExistentTimeError")

The way you seem to be doing it, would work fine for both timezone aware and naive datetime objects. If you want to also add the timezone to your string, you can simply add add it with %z or %Z, or using the isoformat method:

>>> from datetime import timedelta, datetime, tzinfo

>>> class UTC(tzinfo):
...     def utcoffset(self, dt):
...         return timedelta(0)
... 
...     def dst(self, dt):
...         return timedelta(0)
... 
...     def tzname(self,dt):
...          return "UTC"

>>> source = datetime(2010, 7, 1, 0, 0, tzinfo=UTC())
>>> repr(source)
datetime.datetime(2010, 7, 1, 0, 0, tzinfo=<__main__.UTC object at 0x1054107d0>)

# %Z outputs the tzname
>>> source.strftime("%Y-%m-%d %H:%M:%S %Z")
'2010-07-01 00:00:00 UTC'

# %z outputs the UTC offset in the form +HHMM or -HHMM
>>> source.strftime("%Y-%m-%d %H:%M:%S %z")
'2010-07-01 00:00:00 +0000'

# isoformat outputs the offset as +HH:MM or -HH:MM
>>> source.isoformat()
'2010-07-01T00:00:00+00:00'