Sachverhalt: A. A.a. X._ wurde am 16. April 1990 als Staatsangehöriger von Jamaika geboren. Am 29. August 2008 reiste er erstmals in die Schweiz ein, wo er sich bis zum 13. November 2008 bewilligungsfrei aufhielt. Am 22. November 2008 heiratete er in Jamaika die in der Schweiz aufenthaltsberechtigte jamaikanische Staatsangehörige Y._. Die von den Eheleuten eingereichten Gesuche um Einreise- und Aufenthaltsbewilligung zugunsten von X._ wies das Migrationsamt des Kantons Zürich (nachfolgend: Migrationsamt) am 5. Juni 2009 ab. A.b. Am 25. August 2009 reiste X._ von Belgien her mit einem bis zum 31. August 2009 gültigen Schengen-Visum erneut in die Schweiz ein und ersuchte um Erteilung einer Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Das Migrationsamt teilte ihm am 29. September 2009 mit, infolge Ablaufs der bewilligten Aufenthaltsdauer sei er zur Ausreise verpflichtet. Der Aufforderung, die Schweiz bis zum 9. Oktober 2009 zu verlassen, kam X._ nicht nach und hielt sich in der Folge widerrechtlich in der Schweiz auf. Am 5. November 2009 wurde X._ in Ausschaffungs- bzw. Durchsetzungshaft gesetzt. Die Staatsanwaltschaft Limmattal/Albis sprach ihn am 6. November 2009 des rechtswidrigen Aufenthalts schuldig und verurteilte ihn zu einer bedingten Geldstrafe von 15 Tagessätzen zu je Fr. 30.--. A.c. Nachdem das Bundesamt für Migration auf ein am 7. Dezember 2009 gestelltes Asylgesuch am 27. Januar 2010 nicht eingetreten war, erliess es am 10. Februar 2010 ein dreijähriges Einreiseverbot. Die für den 19. Februar 2010 bzw. 24. März 2010 geplante Rückführung nach Jamaika scheiterte beide Male am renitenten Verhalten von X._. A.d. Mit Urteil des Bezirksgerichts Dietikon vom 7. Juli 2010 wurde die Ehe zwischen X._ und Y._ geschieden. Die am 7. Juni 2009 geborene gemeinsame Tochter Z._ wurde (zusammen mit einem vor der Eheschliessung geborenen Sohn der Ehefrau, dessen Vater nicht X._ ist) unter die elterliche Sorge der Mutter gestellt. X._ wurde kein Besuchsrecht erteilt. A.e. Am 14. Oktober 2010 wurde X._ aus der Durchsetzungshaft entlassen und heiratete am 21. Oktober 2010 die in Jamaika geborene Schweizer Bürgerin W._. Am 25. Oktober 2010 beantragte er die Erteilung einer Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Mit Urteil des Bezirksgerichts Zürich vom 18. April 2011 wurde X._ eines Verbrechens gegen das Betäubungsmittelgesetz (BetmG; SR 812.121) schuldig gesprochen und zu einer bedingten Freiheitsstrafe von 22 Monaten verurteilt. Nach Gewährung des rechtlichen Gehörs wies das Migrationsamt das Gesuch um Erteilung einer Aufenthaltsbewilligung am 11. August 2011 ab und setzte X._ eine Ausreisefrist bis zum 15. November 2011. Am 11. November 2011 kam die gemeinsame Tochter V._ zur Welt. A.f. Am 16. Dezember 2011 verhängte das Bundesamt für Migration ein bis zum 15. Dezember 2016 gültiges Einreiseverbot gegen X._. Zwischen Januar 2012 und Juni 2012 wurde er drei Mal in Haft genommen. Der Aufforderung, die Schweiz unverzüglich selbständig zu verlassen, kam er nicht nach. Mit Strafbefehl der Staatsanwaltschaft Zürich-Limmat vom 6. Juli 2012 wurde X._ wegen vorsätzlichen rechtswidrigen Aufenthalts zu einer Geldstrafe von 90 Tagessätzen zu je Fr. 30.-- verurteilt. Die am 6. November 2009 bedingt ausgesprochene Geldstrafe wurde für vollziehbar erklärt und die Probezeit der am 18. April 2011 bedingt ausgesprochenen Freiheitsstrafe um ein Jahr verlängert. A.g. Auf einen am 8. Februar 2012 erhobenen Rekurs gegen die Verfügung des Migrationsamts vom 11. August 2011 trat die Sicherheitsdirektion des Kantons Zürich (nachfolgend: Sicherheitsdirektion) am 11. April 2012 wegen Verspätung nicht ein. B. Am 13. Juni 2012 stellte X._ erneut ein Gesuch um Erteilung einer Aufenthaltsbewilligung im Rahmen des Familiennachzugs; dieses wurde am 21. Juni 2012 abgewiesen. Den dagegen erhobenen Rekurs wies die Sicherheitsdirektion am 25. Juli 2012 ab. Das Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) bestätigte diesen Entscheid auf Beschwerde hin mit Urteil vom 13. März 2013. C. X._ erhebt am 19. April 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das angefochtene Urteil aufzuheben und ihm die Aufenthaltsbewilligung zu erteilen; eventualiter sei die Angelegenheit zur Vornahme weiterer Abklärungen und zu neuer Entscheidung an das Verwaltungsgericht oder an das Migrationsamt zurückzuweisen. Zudem beantragt X._ die Gewährung der unentgeltlichen Prozessführung unter Beiordnung seines Rechtsvertreters als unentgeltlichen Rechtsbeistand. Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Sicherheitsdirektion hat auf eine Vernehmlassung verzichtet. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde. 