Sachverhalt: A. Der pakistanische Staatsbürger X._ (geb. 15. Januar 1979) reiste im August 2000 in die Schweiz ein, um im Kanton Luzern eine Hotelfachschule zu besuchen und erhielt eine befristete Aufenthaltsbewilligung als Schüler bzw. Servicepraktikant, die zuletzt bis zum 14. August 2004 verlängert wurde. Am 4. Oktober 2004 heiratete X._ eine im Kanton Luzern niederlassungsberechtigte portugiesische Staatsangehörige. Gestützt auf die Heirat erhielt X._ eine bis zum 4. Oktober 2009 gültige Aufenthaltsbewilligung EG/EFTA. Am 25. Februar 2008 trennte sich X._ von seiner Ehefrau, der gemeinsame Haushalt wurde aufgehoben und die Ehefrau zog weg. X._, dessen Aufenthaltsort unbekannt war, wurde von der Einwohnerkontrolle gleichen Datums abgemeldet. X._ wohnte in der Folge im Kanton Zürich, ohne sich dort anzumelden, und arbeitete ab 16. September 2009 als Service-Mitarbeiter in einem Hotel in Zürich. Am 19. Januar 2010 ersuchte X._ das Migrationsamt des Kantons Zürich um Verlängerung seiner bis zum 4. Oktober 2009 gültig gewesenen Aufenthaltsbewilligung. Ohne den Entscheid über die Verlängerung seiner Aufenthaltsbewilligung abzuwarten und ohne Rückreisevisum reiste X._ aber bereits am 4. Februar 2010 nach Pakistan, um dort seine erkrankte Mutter zu besuchen. Bei der Schweizerischen Botschaft in Islamabad beantragte X._ am 4. Mai 2010 ein Visum für einen langfristigen Aufenthalt in der Schweiz, wobei er als Aufenthaltszweck "Familiennachzug" angab. Mit E-Mail vom 20. Mai 2010 wendete sich X._ betreffend sein Visumsgesuch direkt an das Migrationsamt des Kantons Zürich. Am 7. April 2011 liess X._ beim Migrationsamt ein weiteres Mal um Verlängerung seiner bis zum 4. Oktober 2009 gültig gewesenen Aufenthaltsbewilligung ersuchen. Am 18. Mai 2011 wurde die kinderlose Ehe von X._ geschieden. B. Mit Verfügung vom 13. Juli 2011 stellte das Migrationsamt fest, die Aufenthaltsbewilligung von X._ sei erloschen, und wies seine Gesuche vom 19. Januar 2010 und 4. Mai 2011 um Verlängerung der Aufenthaltsbewilligung bzw. um Bewilligung der Wiedereinreise in die Schweiz ab. Die dagegen von X._ erhobenen kantonalen Rechtsmittel blieben ohne Erfolg. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 23. Oktober 2012 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Zürich vom 19. September 2012 aufzuheben, das Migrationsamt des Kantons Zürich anzuweisen, die Aufenthaltsbewilligung des Beschwerdeführers zu verlängern oder ihm diese wieder zu erteilen, eventualiter die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem ersucht X._ um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. Die Sicherheitsdirektion des Kantons Zürich sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Verwaltungsgericht des Kantons Zürich hat auf Vernehmlassung verzichtet. Das Migrationsamt des Kantons Zürich liess sich nicht vernehmen.