Sachverhalt:
A.
A._ (geb. 1990), Staatsangehöriger von Pakistan, reiste am 21. August 2015 in die Schweiz ein und ersuchte um Asyl. Mit Verfügung vom 28. Mai 2018 wies das Staatssekretariat für Migration (SEM) das Asylgesuch ab. Die dagegen erhobene Beschwerde wurde mit rechtskräftigem Urteil des Bundesverwaltungsgerichts vom 16. Oktober 2018 abgewiesen. A._ wurde eine Frist zum Verlassen der Schweiz bis am 19. November 2018 angesetzt.
B.
Am 11. Juli 2018 reichte A._ beim Zivilstandsamt der Stadt Zürich ein Ehevorbereitungsgesuch ein. Am 13. November 2018 ersuchte er um Erteilung einer Kurzaufenthaltsbewilligung zwecks Vorbereitung der Ehe mit der in der Schweiz aufenthaltsberechtigten B._ (geb. 1984), Staatsangehörige von Eritrea. Mit Verfügung vom 16. November 2018 wies das Migrationsamt des Kantons Zürich das Gesuch ab.
Einen dagegen erhobenen Rekurs von A._ wies die Rekursabteilung der Sicherheitsdirektion des Kantons Zürich mit Entscheid vom 16. April 2019 ab, soweit er nicht gegenstandslos geworden war. Sie setzte A._ keine neue Frist zum Verlassen der Schweiz an, da er als rechtskräftig weggewiesen gelte und die Schweiz daher unverzüglich zu verlassen habe.
Mit Urteil vom 21. August 2019 wies das Verwaltungsgericht des Kantons Zürich, 2. Abteilung, eine gegen diesen Entscheid erhobene Beschwerde ab.
C.
Mit Eingabe vom 30. September 2019 (Postaufgabe) reicht A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht ein. Er beantragt, das Urteil des Verwaltungsgerichts vom 21. August 2019 sei aufzuheben und das Verfahren sei zwecks rechtsgenüglicher Sachverhaltsfeststellung, Beweisabnahme und Neubeurteilung an die Vorinstanz zurückzuweisen. Eventualiter sei das Migrationsamt anzuweisen, ihm eine (Kurz-) Aufenthaltsbewilligung zwecks Vorbereitung des Eheschlusses zu erteilen. Prozessual beantragt er, das Migrationsamt sei anzuweisen, für die Dauer des Verfahrens von jeglichen Wegweisungsvollzugshandlungen Abstand zu nehmen. Zudem ersucht er um die unentgeltliche Prozessführung und Verbeiständung. Schliesslich stellt er den Antrag, es sei das Ehevorbereitungsdossier des Zivilstandsamts der Stadt Zürich betreffend ihn und seine Partnerin amtshilfeweise beizuziehen.
Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde und des Gesuchs um aufschiebende Wirkung. Die Sicherheitsdirektion, Rekursabteilung, verzichtet auf Vernehmlassung. Das Migrationsamt des Kantons Zürich und das Staatssekretariat für Migration (SEM) liessen sich nicht vernehmen.
Mit Verfügung vom 23. Oktober 2019 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts das Gesuch um Erlass vorsorglicher Massnahmen gutgeheissen und angeordnet, dass während des bundesgerichtlichen Verfahrens alle Vollziehungsvorkehrungen zu unterbleiben haben.

Erwägungen:
1.
1.1. Auf dem Gebiet des Ausländerrechts ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide ausgeschlossen, welche Bewilligungen betreffen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (<ref-law>). Für das Eintreten genügt, wenn der Betroffene in vertretbarer Weise dartut, dass potenziell ein Anspruch auf die beantragte Bewilligung besteht. Ob die erforderlichen Voraussetzungen hierfür gegeben sind, bildet Gegenstand der materiellen Beurteilung und nicht des Eintretens (<ref-ruling> E. 2.5 S. 315; <ref-ruling> E. 1.1 S. 179; Urteil 2C_117/2019 vom 7. Juni 2019 E. 1.1).
1.2. Der Beschwerdeführer macht geltend, eine in der Schweiz aufenthaltsberechtigte Staatsangehörige von Eritrea heiraten zu wollen. Die Verweigerung der beantragten Bewilligung vereitle sein Recht auf Ehe (<ref-law> und Art. 8 in Verbindung mit Art. 12 EMRK). Aufgrund seines Sachvortrags ist eine Verletzung von Art. 12 EMRK bzw. 14 BV nicht zum Vornherein auszuschliessen. Da auch die übrigen Sachurteilsvoraussetzungen gegeben sind (Art. 42, Art. 82 lit. a i.V.m. Art. 86 Abs. 1 lit. d, Art. 89 Abs. 1, Art. 90 und Art. 100 Abs. 1 BGG), ist auf die Beschwerde einzutreten.
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundes- und Völkerrecht gerügt werden (Art. 95 lit. a und b BGG). Bei der Prüfung wendet das Bundesgericht das Recht von Amtes wegen an (<ref-law>; <ref-ruling> E. 4.4.5 S. 157) und verfügt es über volle Kognition (<ref-law>; <ref-ruling> E. 2 S. 236). Die Verletzung von verfassungsmässigen Individualrechten (einschliesslich der Grundrechte) und von kantonalem Recht prüft das Bundesgericht nur, soweit eine solche Rüge in der Beschwerde überhaupt vorgebracht und ausreichend begründet worden ist (qualifizierte Rüge- und Begründungspflicht gemäss <ref-law>; <ref-ruling> E. 1.7.2 S. 106).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die tatsächlichen Feststellungen der Vorinstanz nur berichtigen oder ergänzen, sofern sie offensichtlich unrichtig sind oder auf einer anderen Rechtsverletzung im Sinne von <ref-law> beruhen (<ref-law>).
2.3. Das Vorbringen von Tatsachen, die sich erst nach dem angefochtenen Entscheid ereigneten oder entstanden (echte Noven), ist vor Bundesgericht unzulässig (<ref-ruling> E. 1.2 S. 22 f. mit Hinweisen). Unbeachtlich im vorliegenden bundesgerichtlichen Verfahren sind daher das Schreiben des Rechtsvertreters des Beschwerdeführers vom 29. August 2019 an das SEM, das Schreiben des SEM vom 3. September 2019 an die Stadt Zürich, Bevölkerungsamt, sowie die E-Mail des Teamleiters Zivilstandsamt der Stadt Zürich vom 19. September 2019 an den Rechtsvertreter des Beschwerdeführers.
3.
Streitgegenstand des bundesgerichtlichen Verfahrens bildet die Frage, ob der Beschwerdeführer Anspruch auf die Erteilung einer (Kurz-) Aufenthaltsbewilligung zwecks Vorbereitung der Heirat hat.
Nach der Rechtsprechung sind die Migrationsbehörden im Hinblick auf Art. 12 EMRK bzw. <ref-law> in Konkretisierung des Gesetzeszwecks von <ref-law> gehalten, eine (Kurz-) Aufenthaltsbewilligung zur Vorbereitung der Ehe zu erteilen, wenn keine Hinweise dafür bestehen, dass die ausländische Person rechtsmissbräuchlich handelt (Scheinehe, missbräuchliche Anrufung der Familiennachzugsbestimmungen usw.), und "klar" erscheint, dass sie nach der Heirat mit dem Ehepartner in der Schweiz wird verbleiben können, d.h. sie auch die weiteren hierfür erforderlichen Voraussetzungen erfüllt (<ref-ruling> E. 3.5.2 S. 48; <ref-ruling> E. 4 und 5 S. 46 ff.; <ref-ruling> E. 3.7 S. 359 f.). Die Kurzaufenthaltsbewilligung zwecks Vorbereitung des Eheschlusses soll schliesslich nur erteilt werden, wenn mit diesem bzw. dem Erhalt der hierfür zivilrechtlich erforderlichen Papiere und Bestätigungen in absehbarer Zeit gerechnet werden kann; die (vorübergehende) Legalisierung des Aufenthalts mit Blick auf den Eheschluss darf nicht dazu dienen, die Anwesenheit längerfristig zu sichern (Urteile 2C_117/2019 vom 7. Juni 2019 E. 3; 2C_880/2017 vom 3. Mai 2018 E. 4.3; 2C_702/2011 vom 23. Februar 2012 E. 4.4). Diese Rechtsprechung gilt trotz des Vorrangs des Asylverfahrens (<ref-law> [SR 142.31]) und der Bindung an die Bundesgesetze (<ref-law>) auch für abgewiesene Asylsuchende, die erst dank der Heirat einen ausländerrechtlichen Bewilligungsanspruch erwerben (vgl. BGE <ref-ruling> E. 3 S. 45 f.; <ref-ruling> E. 3.5 S. 356 ff. und E. 3.7 S. 359 f.; Urteil 2C_962/2013 vom 13. Februar 2015 E. 4.2).
4.
Der Beschwerdeführer rügt eine falsche Sachverhaltsfeststellung sowie eine Verletzung seines rechtlichen Gehörs (<ref-law>) und sinngemäss des Untersuchungsgrundsatzes. Er wirft dem Verwaltungsgericht vor, es sei zu Unrecht auf seinen prozessualen Antrag auf Beizug des Ehevorbereitungsdossiers des Zivilstandsamts betreffend ihn und seine Partnerin nicht eingetreten. Aufgrund des engen Konnexes und der gegenseitigen Abhängigkeit der Verfahren vor dem Zivilstandsamt und der Migrationsbehörde im vorliegenden Verfahren sei die Bedeutung des Ehevorbereitungsdossiers für die Frage der Absehbarkeit des Eheschlusses geradezu offensichtlich. Ob der Eheschluss in absehbarer Zeit erfolgen könne, entscheide sich erfahrungsgemäss an der Frage, ob die für die Eheschliessung beim Zivilstandsamt notwendige Dokumentation innert Frist beigebracht werden könne. Allfällige Dokumentenprüfungen würden regelmässig vom Zivilstandsamt bzw. in dessen Auftrag von der Schweizerischen Vertretung im Ausland vorgenommen. Für die Einschätzung des Zeithorizonts bis zum Eheschluss sei regelmässig der Stand bzw. die voraussichtliche Dauer der Dokumentenprüfung entscheidend. Daher habe die Vorinstanz auch nicht willkürfrei in antizipierter Beweiswürdigung annehmen dürfen, dass die Akten des Zivilstandsamts unter keinen Umständen geeignet seien, die eigene Einschätzung zu ändern.
4.1. Gemäss <ref-law> kann die Feststellung des Sachverhalts nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-ruling> E. 2.2 S. 313; vgl. E. 2.2 hiervor). Eine Sachverhaltsfeststellung ist nicht schon dann offensichtlich unrichtig, wenn Zweifel bestehen, sondern erst, wenn sie eindeutig und augenfällig unzutreffend ist (<ref-ruling> E. 3.1 S. 44; Urteil 8C_416/2015 vom 30. September 2015 E. 1.2). Wird die vorinstanzliche Beweiswürdigung beanstandet, so ist die Kognition des Bundesgerichts auf Willkür beschränkt (vgl. Urteil 2C_66/2016 vom 12. Oktober 2016 E. 2.2).
4.2. Das rechtliche Gehör (<ref-law>) verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt (<ref-ruling> E. 9.2 S. 65; <ref-ruling> E. 5.2 S. 236; Urteile 2C_562/2019 vom 12. November 2019 E. 3.2; 2C_641/2019 vom 3. Oktober 2019 E. 2.2). Dazu gehört, dass die Behörde alle erheblichen und rechtzeitigen Vorbringen der Parteien würdigt und die ihr angebotenen Beweise abnimmt, wenn diese zur Abklärung des Sachverhalts tauglich erscheinen (<ref-ruling> E. 3.3 S. 64; Urteil 2C_866/2017 vom 7. März 2018 E. 3.1.1). Keine Verletzung des rechtlichen Gehörs liegt vor, wenn ein Gericht darauf verzichtet, beantragte Beweise abzunehmen, weil es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 3.1.3 S. 435; <ref-ruling> E. 5.3 S. 236; <ref-ruling> E. 5.3 S. 148; Urteile 2C_202/2018 vom 19. Juli 2019 E. 4.2; 2C_272/2016 vom 28. April 2016 E. 2.2). Bei der Abweisung von Beweisanträgen in antizipierter Beweiswürdigung ist jedoch Zurückhaltung geboten; es darf nicht leichthin angenommen werden, dass das Beweisergebnis aufgrund der bereits abgenommenen Beweise feststeht. Lehnt die Behörde den Beweisantrag ab, hat sie nicht nur darzulegen, weshalb sie aufgrund der bereits abgenommenen Beweise eine bestimmte Überzeugung gewonnen hat, sondern grundsätzlich auch, weshalb die beantragte Beweismassnahme aus ihrer Sicht nichts an ihrer Überzeugung zu ändern vermag (Urteile 2C_866/2017 vom 7. März 2018 E. 3.1.1; 2C_400/2015 vom 31. Mai 2016 E. 4.2).
4.3. Gemäss dem Untersuchungsgrundsatz müssen die Migrationsbehörden den rechtserheblichen Sachverhalt grundsätzlich von Amtes wegen feststellen (vgl. Urteil 2C_61/2014 vom 5. Januar 2015 E. 3.2.1). Der Untersuchungsgrundsatz wird aber durch die Mitwirkungspflicht der Parteien relativiert (<ref-law> [SR 142.20]). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden können (vgl. <ref-ruling> E. 8.6.4 S. 496 f.; Urteile 2C_613/2019 vom 14. November 2019 E. 3.6.4; 2C_118/2017 vom 18. August 2017 E. 4.2). Als Korrelat zur Mitwirkungspflicht der Parteien sind die Behörden jedoch gehalten, rechtzeitig und formrichtig angebotene Beweismittel zu rechtserheblichen Tatsachen abzunehmen (<ref-ruling> E. 4.3 S. 13; <ref-ruling> E. 2 S. 242; Urteil 2C_202/2018 vom 19. Juli 2019 E. 4.3).
4.4. Die Vorinstanz ist auf den Antrag des Beschwerdeführers auf Beizug des Ehevorbereitungsdossiers des Zivilstandsamts nicht eingetreten, weil der Beschwerdeführer diesen nicht begründet habe. Subsidiär führte das Verwaltungsgericht aus, der Antrag hätte, selbst wenn darauf einzutreten wäre, abgewiesen werden müssen, weil das Zivilstandsamt die Trauung mit Verfügung vom 21. Februar 2019 verweigert und das nämliche Gesuchsverfahren eingestellt habe. Vor diesem Hintergrund sei nicht anzunehmen, dass der Beschwerdeführer aus dem Ehevorbereitungsdossier etwas zu seinen Gunsten hätte ableiten können (vgl. E. 1.2 des angefochtenen Urteils).
4.5.
4.5.1. Aus den Akten ergibt sich, dass der Beschwerdeführer seinen Antrag auf Beizug des Ehevorbereitungsdossiers des Zivilstandsamts im vorinstanzlichen Verfahren mit einer Änderung der Ausgangslage seit dem Entscheid der Sicherheitsdirektion begründet hatte. Er hatte im Wesentlichen behauptet, dass das Prüfungsverfahren der verschiedenen Unterlagen weit fortgeschritten gewesen sei, so dass der Eheschluss in absehbarer Zeit werde erfolgen können. Sämtliche für die Heirat nötigen Unterlagen seien dem Zivilstandsamt abgegeben worden, so insbesondere die Todesbescheinigung des früheren Ehemannes seiner Partnerin sowie eine neue, am 13. März 2019 ausgestellte Ledigkeitsbestätigung des Beschwerdeführens. Zwar habe seine Partnerin die Originalunterlagen betreffend den Tod ihres früheren Ehemannes bereits am 25. Januar 2019 dem Zivilstandsamt abgegeben, doch habe dieses die Dokumente nicht überprüfen lassen. Die Frage, inwiefern die besagte Todesbescheinigung einer Überprüfung durch die schweizerische Vertretung in Äthiopien zu unterziehen sei, sei im Zeitpunkt der Beschwerdeeinreichung vor der Vorinstanz Gegenstand von Abklärungen beim Zivilstandsamt gewesen. Hinsichtlich seiner neu ausgestellten Ledigkeitsbestätigung hatte der Beschwerdeführer ausgeführt, diese sei zu Handen des SEM sichergestellt worden. In der Folge habe er beim SEM um eine erneute Überprüfung dieses Dokuments ersucht; das SEM habe sich jedoch für unzuständig erklärt, die fragliche Bestätigung an die schweizerische Vertretung in Äthiopien zu senden, und auf die Zuständigkeit des Zivilstandsamts verwiesen. Dort habe der Beschwerdeführer um eine entsprechende Prüfung der Ledigkeitserklärung im Hinblick auf ein neues Ehevorbereitungsverfahren ersucht. Für die Prüfung der Beschwerde dürfe daher der Beizug der Akten vom Zivilstandsamt unumgänglich sein.
4.5.2. Es ist somit festzuhalten, dass der Beschwerdeführer seinen Antrag auf Beizug der Akten des Zivilstandsamts im vorinstanzlichen Verfahren zumindest summarisch begründet hatte. Mit Blick auf <ref-law> ist zudem zu beachten, dass mindestens eine gerichtliche Instanz im Kanton den Sachverhalt frei zu prüfen und das massgebende Recht von Amtes wegen anzuwenden hat. Dies schliesst zwar nicht aus, dass in einer mit <ref-law> vergleichbaren Weise gewisse Anforderungen an die Begründung von Rechtsmitteln gestellt werden. Eine eigentliche Rügepflicht, wie sie vor Bundesgericht in bestimmten Fällen gilt (<ref-law>), ist im kantonalen Verfahren jedoch unzulässig, wenn, wie im vorliegenden Fall, das Verwaltungsgericht als einzige richterliche Instanz entscheidet (vgl. <ref-ruling> E. 6.5 S. 314 f.; Urteile 2C_286/2017 vom 29. Mai 2017 E. 3.2; 1C_265/2017 vom 25. Juni 2018 E. 2.4). Vor diesem Hintergrund durfte die Vorinstanz nicht mangels Begründung des Antrags auf Nichteintreten erkennen.
4.6. Im Folgenden ist zu prüfen, ob die Vorinstanz willkürfrei in antizipierter Beweiswürdigung auf den Beizug der Akten des Zivilstandsamts hätte verzichten dürfen (vgl. E. 4.2 hiervor).
4.6.1. Das Verwaltungsgericht hat im Sinne einer Eventualbegründung festgehalten, es sei nicht anzunehmen, dass der Beschwerdeführer aus dem Ehevorbereitungsdossier etwas zu seinen Gunsten hätte ableiten können. Dabei hat es sich vorwiegend auf die Verfügung des Zivilstandsamts vom 21. Februar 2019 gestützt, mit welcher das Ehevorbereitungsverfahren eingestellt wurde (vgl. E. 1.2 des angefochtenen Urteils). Ferner hat das Verwaltungsgericht auf Abklärungen der Sicherheitsdirektion vom 19. März 2019 hingewiesen, wonach die Partnerin des Beschwerdeführers zu jenem Zeitpunkt immer noch als verheiratet gemeldet gewesen sei. Weitere Abklärungen hinsichtlich des Stands des Verfahrens vor dem Zivilstandsamt hat die Vorinstanz nicht vorgenommen (vgl. E. 2.3 des angefochtenen Urteils).
4.6.2. Der Antrag des Beschwerdeführers auf Beizug des Ehevorbereitungsdossiers stand im Zusammenhang mit dem Nachweis der Voraussetzungen für die Erteilung einer (Kurz-) Aufenthaltsbewilligung zwecks Vorbereitung der Ehe. Das zentrale Beweisthema des vorinstanzlichen Verfahrens war, ob die Partnerin des Beschwerdeführers tatsächlich verwitwet sei und ob eine gültige Ledigkeitsbestätigung des Beschwerdeführers vorliege.
4.6.3. Es erscheint naheliegend, dass zwischen dem Verfahren vor dem Zivilstandsamt und dem vorliegenden Verfahren um Erteilung einer (Kurz-) Aufenthaltsbewilligung zwecks Vorbereitung der Heirat, wie vom Beschwerdeführer behauptet, ein enger Konnex besteht. Die Akten des Zivilstandamts erscheinen als taugliches und sachdienliches Beweismittel für die Abklärung der Frage, ob die für die Eheschliessung notwendigen Dokumente dem Zivilstandsamt vorliegen und wie weit deren Prüfung fortgeschritten ist. Zwar trifft es zu, wie von der Vorinstanz ausgeführt, dass das Ehevorbereitungsverfahren mit Verfügung des Zivilstandsamts vom 21. Februar 2019 eingestellt wurde (vgl. E. 2.3 des angefochtenen Urteils). Der besagten Verfügung kann jedoch entnommen werden, dass die Einstellung des Verfahrens einzig damit begründet wurde, dass der Beschwerdeführer den Nachweis über seinen rechtmässigen Aufenthalt in der Schweiz nicht hatte erbringen können. In der Folge wurde auch die Trauung des Beschwerdeführers mit seiner Partnerin gestützt auf <ref-law> in Verbindung mit Art. 67 Abs. 3 der Zivilstandsverordnung vom 28. April 2004 (ZStV; SR 211.112.2) verweigert. Zu jenem Zeitpunkt war die Erteilung einer (Kurz-) Aufenthaltsbewilligung zwecks Vorbereitung der Ehe jedoch Gegenstand des Rekursverfahrens vor der Sicherheitsdirektion. Zur Frage, ob ein Eheschluss in absehbarer Zeit möglich gewesen wäre, lassen sich der besagten Verfügung des Zivilstandsamts keine Hinweise entnehmen.
4.6.4. Wie bereits dargelegt, hatte der Beschwerdeführer im vorinstanzlichen Verfahren ausgeführt, dass er seit der Einstellung des Ehevorbereitungsverfahrens am 21. Februar 2019 weitere Schritte unternommen habe, um nachzuweisen, dass der Eheschluss in absehbarer Zeit erfolgen könnte, und dass die Prüfung der eingereichten Unterlagen weit fortgeschritten sei (vgl. E. 4.5.1 hiervor). Im bundesgerichtlichen Verfahren macht er zudem geltend, dass er am 6. Juni 2019 beim Zivilstandsamt um die Wiederaufnahme des Ehevorbereitungsverfahrens ersucht habe. Schliesslich behauptet er, dass die Verfahrensverzögerungen nicht von ihm zu verantworten, sondern hauptsächlich auf Versäumnisse der involvierten Behörden zurückzuführen seien.
Ob die Behauptungen des Beschwerdeführers zutreffen, bedarf zumindest weiterer Abklärungen. Der Stand des Verfahrens vor dem Zivilstandsamt bzw. der Prüfung der eingereichten Dokumente ist für die Beurteilung der Absehbarkeit des Eheschlusses und somit auch für den Ausgang des Verfahrens von Bedeutung. Das Verwaltungsgericht hat nicht überzeugend dargelegt, weshalb die Akten des Zivilstandsamts nicht geeignet wären, diese Frage zu klären (vgl. E. 4.2 hiervor). Seine Vermutungen, wonach sich die Ausgangslage seit dem Entscheid der Sicherheitsdirektion nicht mehr geändert habe, reichen nicht aus, um abschliessend zu prüfen, ob in absehbarer Zeit mit einem Eheschluss zu rechnen ist. Soweit die Vorinstanz dem Beschwerdeführer schliesslich entgegenhält, er habe seine Partnerin noch nicht geheiratet, ist dieser Vorwurf haltlos, zumal die Erteilung einer Aufenthaltsbewilligung zwecks Heirat Voraussetzung für die Eheschliessung bildet und die Frage, ob der Beschwerdeführer einen Anspruch darauf hat, Gegenstand des vorliegenden Verfahrens ist.
5.
Nach dem Gesagten hätte die Vorinstanz den Antrag des Beschwerdeführers auf Beizug der Akten des Zivilstandsamtes nicht in antizipierter Beweiswürdigung abweisen dürfen. Indem sie das tat, verletzte sie das rechtliche Gehör des Beschwerdeführers (<ref-law>) sowie den Untersuchungsgrundsatz.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist daher gutzuheissen, und das angefochtene Urteil des Verwaltungsgerichts des Kantons Zürich vom 21. August 2019 ist aufzuheben. Die Sache wird zu neuem Entscheid im Sinne der Erwägungen an das Verwaltungsgericht des Kantons Zürich zurückgewiesen. Dieses wird unter Beizug der Akten des Zivilstandsamts betreffend die Ehevorbereitung des Beschwerdeführers und seiner Partnerin erneut darüber zu befinden haben, ob die Voraussetzungen für die Erteilung einer (Kurz-) Aufenthaltsbewilligung erfüllt sind bzw. ob der Eheschluss in absehbarer Zeit erfolgen könnte. Damit erübrigt sich, auf die weiteren Rügen des Beschwerdeführers einzugehen.
6.
Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Zürich hat dem anwaltlich vertretenen Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung auszurichten (<ref-law>). Das Gesuch um Gewährung der unentgeltlichen Rechtspflege im bundesgerichtlichen Verfahren wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, und das Urteil des Verwaltungsgerichts des Kantons Zürich vom 21. August 2019 wird aufgehoben. Die Sache wird zu neuem Entscheid im Sinne der Erwägungen an das Verwaltungsgericht des Kantons Zürich zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 2'500.-- zu bezahlen.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 2. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 17. Januar 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Ivanov