Sachverhalt:
A.
A.a. A._ (geb. 1968), Staatsangehöriger von Sierra Leone, und B._ (geb. 1977), Staatsangehörige von Nigeria, stellten am 27. März 2015 beim Zivilstandsamt der Stadt Zürich ein Gesuch um Vorbereitung der Eheschliessung. Mit Verfügung vom 30. September 2015 verweigerte das Zivilstandsamt die Fortsetzung des Ehevorbereitungsverfahrens und die Trauung. Es befand, A._ habe seinen rechtmässigen Aufenthalt in der Schweiz nicht nachgewiesen (<ref-law> in Verbindung mit Art. 67 Abs. 3 der Zivilstandsverordnung [ZStV; SR 211.112.2]). Eine dagegen eingereichte Beschwerde beim Gemeindeamt des Kantons Zürich blieb ohne Erfolg (Verfügung vom 22. Januar 2016).
A.b. Am 22. Februar 2016 erhob A._ Beschwerde beim Verwaltungsgericht des Kantons Zürich. In der Sache beantragte er, dass ihm unter Entschädigungsfolge und Aufhebung der gemeindeamtlichen Verfügung das Eingehen der Ehe auf schweizerischem Hoheitsgebiet zu gestatten sei. In prozessualer Hinsicht ersuchte er für das verwaltungsgerichtliche Verfahren um unentgeltliche Rechtspflege.
A.c. Mit Auszug aus dem Protokoll vom 29. Februar 2016 wies der Präsident des Verwaltungsgerichts das Gesuch des Beschwerdeführers um Befreiung von der Kostenvorschusspflicht (Bst. A.b) ab. Zugleich forderte er A._ auf, binnen vierzehn Tagen einen Kostenvorschuss von Fr. 2'060.-- zu leisten, verbunden mit der Androhung, dass im Falle der Nichtbezahlung auf das Rechtsmittel nicht eingetreten werde.
A.d. Mit Verfügung vom 30. März 2016 stellte das Verwaltungsgericht fest, dass A._ den Kostenvorschuss (Bst. A.c) nicht geleistet hatte. Es trat auf die Beschwerde nicht ein und auferlegte A._ die Gerichtsgebühr von Fr. 1'100.--.
B.
B.a. Mit Beschwerde vom 21. März 2016 wehrt sich A._ (Beschwerdeführer) vor Bundesgericht gegen die verwaltungsgerichtliche Verfügung vom 29. Februar 2016 (Bst. A.c). Er verlangt, "die Kautionierung... aufzuheben" und die Vorinstanz zu verpflichten, "auf das... Beschwerdeverfahren einzutreten" (Verfahren 5A_230/2016). Er beantragte ausserdem, seiner Beschwerde die aufschiebende Wirkung zu erteilen, und ersuchte für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege.
B.b. Mit Verfügung vom 23. März 2016 befahl das Bundesgericht dem Verwaltungsgericht, bis zum Entscheid über das Gesuch um aufschiebende Wirkung alle Vollziehungsvorkehrungen zu unterlassen. Mit Schreiben vom 5. April 2016 informierte das Verwaltungsgericht das Bundesgericht über seinen Nichteintretensentscheid vom 30. März 2016 (Bst. A.d). Darauf schrieb der Präsident der II. zivilrechtlichen Abteilung das Gesuch um aufschiebende Wirkung im Verfahren 5A_230/2016 infolge Gegenstandslosigkeit ab (Verfügung vom 6. April 2016).
B.c. Mit Beschwerde vom 2. Mai 2016 zog der Beschwerdeführer die Nichteintretensverfügung vom 30. März 2016 (Bst. A.d) an das Bundesgericht weiter (Verfahren 5A_330/2016). Er verlangt, die besagte Verfügung aufzuheben und die Sache "zur materiellrechtlichen Entscheidfindung" an das Verwaltungsgericht zurückzuweisen. Auch in diesem Verfahren stellt er das Begehren, seinem Rechtsmittel die aufschiebende Wirkung zuzuerkennen und ihm die unentgeltliche Rechtspflege zu gewähren.
B.d. Der Präsident der II. zivilrechtlichen Abteilung nahm das Gesuch um aufschiebende Wirkung, mit dem der Beschwerdeführer verhindern wollte, bis zu einem Entscheid in der Sache aus der Schweiz ausgeschafft zu werden, als Gesuch um vorsorgliche Massnahmen entgegen und wies es ab (Verfügung vom 9. Mai 2016).
B.e. Mit Schreiben vom 17. Mai 2016 lässt der Beschwerdeführer über seinen Anwalt ausrichten, dass das Zwangsmassnahmengericht des Bezirks Zürich mit Verfügung vom 7. Mai 2016 den Antrag auf Ausschaffungshaft abgewiesen habe und er am gleichen Tag aus dem Flughafengefängnis entlassen worden sei.
B.f. Das Bundesgericht hat sich die vorinstanzlichen Akten überweisen lassen, in der Sache aber keine Vernehmlassungen eingeholt.

Erwägungen:
1.
1.1. Angefochten ist im Verfahren 5A_230/2016 der Entscheid, mit dem das Verwaltungsgericht das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege (hinsichtlich der Befreiung von der Kostenvorschusspflicht) für das kantonale Rechtsmittelverfahren abweist und ihm unter Androhung der Nichteintretensfolge eine Frist zur Sicherstellung der Verfahrenskosten setzt (s. Sachverhalt Bst. A.c). Der Entscheid erging mittels einer selbständigen, vorab eröffneten Verfügung. Er ist also ein Zwischenentscheid, der nach der Rechtsprechung einen nicht wieder gutzumachenden Nachteil im Sinne von Art. 93 Abs. 1 Bst. a BGG bewirken kann (Urteil 5A_790/2014 vom 5. Mai 2015 E. 1). Dass das Verwaltungsgericht nicht als Rechtsmittelinstanz im Sinne von <ref-law> entschieden hat, steht der Zulässigkeit der Beschwerde an das Bundesgericht nicht entgegen (<ref-ruling> E. 2.2 S. 426 f.). Bei Zwischenentscheiden folgt der Rechtsweg demjenigen der Hauptsache (<ref-ruling> E. 2.2 S. 647 f.). Dort geht es um die Zulassung zur Ehevorbereitung und Trauung. Das ist eine öffentlich-rechtliche Angelegenheit, die in unmittelbarem Zusammenhang mit dem Zivilrecht steht und der Beschwerde in Zivilsachen unterliegt (Art. 72 Abs. 2 Bst. b BGG; Urteil 5A_814/2011 vom 17. Januar 2012 E. 1, nicht publ. in: <ref-ruling>). Das gleiche Rechtsmittel ist daher gegen den angefochtenen Zwischenentscheid zulässig.
1.2. Zum andern wehrt sich der Beschwerdeführer im Beschwerdeverfahren 5A_330/2016 dagegen, dass das Verwaltungsgericht auf seine Beschwerde nicht eintritt, mit der er den Entscheid des Gemeindeamts des Kantons Zürich im Streit um die Fortsetzung des Verfahrens zur Ehevorbereitung und Trauung anfocht (s. Sachverhalt Bst. A.d). Das ist ein Endentscheid (<ref-law>) einer letzten kantonalen Instanz, die als oberes Gericht auf Rechtsmittel hin entschieden hat (<ref-law>). Streitig ist eine öffentlich-rechtliche Angelegenheit, die in unmittelbarem Zusammenhang mit dem Zivilrecht steht und der Beschwerde in Zivilsachen unterliegt (Art. 72 Abs. 2 Bst. b BGG; s. E. 1.1).
1.3. Beide Beschwerden (E. 1.1 und 1.2) erfolgten rechtzeitig (<ref-law>). Soweit das Verfahren 5A_230/2016 nicht durch die Verfügung des Verwaltungsgerichts vom 30. März 2016 (s. Sachverhalt Bst. A.d) gegenstandslos geworden ist (s. Sachverhalt Bst. B.b), stellen sich in diesem Verfahren die gleichen rechtlichen Fragen wie im Verfahren 5A_330/2016. Eine allfällige Unrechtmässigkeit des Zwischenentscheids über die unentgeltliche Rechtspflege und den Kostenvorschuss (Verfahren 5A_230/2016) hätte einen Einfluss auf die Begründetheit der Beschwerde gegen den Endentscheid (Verfahren 5A_330/2016), mit dem das Verwaltungsgericht mangels Leistung des Kostenvorschusses auf das kantonale Rechtsmittel nicht eintritt. Die beiden Beschwerdeverfahren 5A_220/2016 und 5A_330/2016 sind deshalb zu vereinigen (<ref-law> i.V.m. <ref-law>).
2.
Im Kern dreht sich der Streit um die Frage, ob die Vorinstanz das kantonale Rechtsmittel des Beschwerdeführers als aussichtslos qualifizieren durfte. Davon hängt der Ausgang des Armenrechtsgesuchs und - im Anschluss daran - der Streit um die Vorschusspflicht ab.
2.1. Dem angefochtenen Entscheid zufolge hätte von der Einforderung eines Kostenvorschusses verzichtet werden können, wenn der Beschwerdeführer Anspruch auf unentgeltliche Rechtspflege gehabt hätte, also nebst anderem sein Rechtsmittel nicht offenkundig aussichtslos erschienen wäre. Diese Voraussetzung hält das Verwaltungsgericht für nicht erfüllt. Es verweist auf die Rechtslage, wonach Verlobte, die nicht Schweizerbürgerinnen oder Schweizerbürger sind, während des Verfahrens zur Vorbereitung der Eheschliessung ihren rechtmässigen Aufenthalt in der Schweiz nachweisen müssen (<ref-law>). Das Verwaltungsgericht macht sich die Erwägungen des Gemeindeamts zu eigen, wonach der Beschwerdeführer diesen Nachweis nicht erbracht habe. Es hält dem Beschwerdeführer bzw. seinem Vertreter vor, dass er um diese Rechtslage wisse, zumal der Vertreter in einem gleich gelagerten Fall für eine andere Person erfolglos das Bundesgericht angerufen habe, und dass es dem Beschwerdeführer ausdrücklich darum gehe, am Ende an den Europäischen Gerichtshof für Menschenrechte gelangen zu können. Die "folglich statthafte Kautionierung" stütze sich einschliesslich der Androhung des Nichteintretens "zu Recht" auf § 65a Abs. 2 i.V.m. § 15 Abs. 2 Bst. b des zürcherischen Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 (VRG; LS 175.2).
2.2. Der Beschwerdeführer macht geltend, einst im Besitze einer Aufenthaltsbewilligung gewesen zu sein, so dass er sich auf Art. 33 und 96 AuG (SR 142.20) berufen könne (Verletzung des rechtlichen Gehörs). Er erachtet es als materielle wie auch als formelle Rechtsverweigerung, wenn sein Anliegen mangels Bezahlung des Kostenvorschusses keine Beurteilung erfahre, insbesondere auch deshalb, weil er im vergangenen Jahr hierzulande Vater geworden sei. Er halte sich nun seit 17 Jahren in der Schweiz auf; ihm müsse daher wegen der Dauer seines Aufenthalts ein Bleiberecht erwachsen. Im Wissen darum, dass dies der Gesetzgeber beim Erlass des neuen Ausländergesetzes nicht vorgesehen habe, sollten bei einem bald zwanzigjährigen Aufenthalt des Ausländers die ausländerrechtlichen Normen in einer Weise zur Anwendung gebracht werden, dass dem Ausländer eine Art von Aufenthaltsbewilligung zugestanden werde. Er strebe eine dritte Ehe an, um endlich eine Frau zu heiraten, die ihm den legalen Aufenthalt in der Schweiz ermögliche. Dies sei im Fall der Mutter seiner Tochter leider nicht der Fall. Sein Anliegen sei legitim und die Vorinstanz mit ihrem Vorgehen der Verfahrenskautionierung keineswegs fair. Es müsse doch zulässig sein, sich nun auch im bundesgerichtlichen Verfahren auf ein Verhältnis zu der unlängst geborenen Tochter zu berufen.
2.3. Die Überlegungen des Beschwerdeführers gehen an der Sache vorbei. Zu Recht erinnert die Vorinstanz daran, dass dem Rechtsvertreter des Beschwerdeführers die Rechtslage aufgrund seiner Beteiligung im Verfahren, das zum Urteil des Bundesgerichts 5A_790/2014 vom 5. Mai 2015 geführt hat, bestens bekannt ist: Bei der Anwendung von <ref-law> klärt das Zivilstandsamt nicht selbst ab, ob sich die Verlobten rechtmässig in der Schweiz aufhalten. Diese Aufgabe obliegt ausschliesslich der Ausländerbehörde. Diese Behörde entscheidet damit auch darüber, ob einem Ausländer allenfalls im Hinblick auf seinen Wunsch, in der Schweiz zu heiraten, der hiesige Aufenthalt während des Vorbereitungsverfahrens zu gestatten ist. Damit hat die Ausländerbehörde auch die Vereinbarkeit von <ref-law> mit der EMRK sicherzustellen (zum Ganzen: <ref-ruling> E. 3.7 S. 359 f.). Es besteht kein Anlass, diese mittlerweile gefestigte Praxis, was die Zusammenarbeit der Zivilstandsämter und der Ausländerbehörden betrifft, zu überdenken. Deshalb ist es auch nicht zu beanstanden, dass die Vorinstanz das kantonale Rechtsmittel in ihrer Verfügung vom 29. Februar 2016 als offensichtlich unbegründet bezeichnet und das Gesuch des Beschwerdeführers um Befreiung von der Kostenvorschusspflicht abweist (s. Sachverhalt Bst. A.c). Dass das Verwaltungsgericht bei dieser Ausgangslage gestützt auf die erwähnten kantonalen Vorschriften einen Kostenvorschuss verlangen durfte, stellt der Beschwerdeführer nicht in Abrede. Weder bestreitet er, dem Kanton Zürich Gebühren von über Fr. 16'000.-- zu schulden, noch behauptet er, dass es sich nicht mit dem Bundesrecht verträgt, die Vorschusspflicht mit unbezahlten Gebührenschulden zu begründen. Auch in dieser Hinsicht hat es mit der Verfügung vom 29. Februar 2016 (s. Sachverhalt Bst. A.c) sein Bewenden.
3.
Was das Verfahren 5A_330/2016 betreffend den Nichteintretensentscheid des Verwaltungsgerichts vom 30. März 2016 angeht, stellt das Verwaltungsgericht in diesem Entscheid fest, dass der Beschwerdeführer den geforderten Vorschuss nicht binnen gesetzter Frist, das heisst nicht bis zum 18. März 2016 geleistet habe. Daraus folgert es, dass sein Rechtsmittel androhungsgemäss nicht an die Hand zu nehmen sei. Mit diesen Erkenntnissen setzt sich der Beschwerdeführer nicht auseinander. Weder reklamiert er, dass die Vorinstanz den Sachverhalt hinsichtlich der (unterbliebenen) Leistung des Vorschusses offensichtlich unrichtig (<ref-law>) festgestellt hat, noch nennt er Gründe, weshalb die Vorinstanz trotz Nichtbezahlung des Gerichtskostenvorschusses auf sein Rechtsmittel hätte eintreten müssen.
4.
Die Beschwerden erweisen sich damit in jeder Hinsicht als unbegründet. Sie sind abzuweisen, soweit überhaupt darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens unterliegt der Beschwerdeführer. Er hat deshalb für die Gerichtskosten aufzukommen (<ref-law>). Dem Kanton Zürich und der Stadt Zürich ist keine Entschädigung geschuldet (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird infolge offensichtlicher Aussichtslosigkeit abgewiesen (<ref-law>). Der Rechtsvertreter des Beschwerdeführers wird darauf hingewiesen, dass sein prozessuales Verhalten nur bei grösstem Wohlwollen nicht als schikanös bezeichnet werden kann. Er wird hiermit ausdrücklich abgemahnt. In ähnlichen Fällen leichtfertigen oder mutwilligen Prozessierens hat der Rechtsvertreter damit zu rechnen, dass das Bundesgericht ihn als Verursacher unnötiger Kosten in die Pflicht nimmt (Art. 66 Abs. 3 und Art. 68 Abs. 4 BGG) und bei der zuständigen Aufsichtsbehörde über die Rechtsanwälte verzeigt.

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 5A_230/2016 und 5A_330/2016 werden vereinigt.
2.
Die Beschwerden werden abgewiesen, soweit darauf einzutreten ist.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird dem Beschwerdeführer, Rechtsanwalt Guido Hensch, dem Zivilstandsamt der Stadt Zürich und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, schriftlich mitgeteilt.
Lausanne, 4. Oktober 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Monn