Sachverhalt: A. A._ (geb. 1964) ist Staatsangehöriger der Dominikanischen Republik. Am 6. November 2008 heiratete er im Heimatland die in der Schweiz niederlassungsberechtigte Landsfrau B._ (geb. 1967). Nach seiner Einreise in die Schweiz am 17. September 2009 erteilte ihm das Migrationsamt des Kantons Zürich (hiernach: Migrationsamt) im Rahmen des Familiennachzugs eine Aufenthaltsbewilligung, welche zuletzt bis zum 16. September 2014 verlängert wurde. Ende November 2013 wurde die eheliche Wohngemeinschaft aufgegeben. B. Mit Verfügung vom 22. Januar 2015 verweigerte das Migrationsamt die Verlängerung der Aufenthaltsbewilligung von A._ und setzte ihm eine Ausreisefrist. Ein Rekurs bei der Sicherheitsdirektion blieb erfolglos (Entscheid vom 27. November 2015). Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 22. Februar 2016 ebenfalls ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten (eventualiter subsidiärer Verfassungsbeschwerde) vom 1. April 2016 beantragt A._ die Aufhebung des vorinstanzlichen Urteils. Ihm sei die Aufenthaltsbewilligung zu verlängern. Eventualiter sei er nach Art. 96 Abs. 2 AuG zu verwarnen. In einem weiteren Eventualantrag verlangt er, es sei ihm eine Ausreisefrist von drei Monaten anzusetzen. Zudem beantragt er die unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren. Mit Präsidialverfügung vom 4. April 2016 wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt. Das Bundesgericht hat die Akten des kantonalen Verfahrens, aber keine Vernehmlassungen eingeholt. D. Am 19. Juli 2016 ging beim Bundesgericht die Mitteilung des Migrationsamts ein, A._ habe sich am 6. Juli 2016 mit der brasilianischen (recte: dominikanischen) Staatsbürgerin C._ (geb. 1971) verheiratet.