Sachverhalt:
A.
A.a. B._ (geb. 1960; Beschwerdeführerin) und A._ (geb. 1978; Beschwerdeführer) ersuchten das Zivilstandsamt der Stadt Zürich erstmals am 10. Januar 2019 um Durchführung eines Ehevorbereitungsverfahrens. Das Zivilstandsamt wies dieses Gesuch am 28. März 2019 ab, weil A._ keinen rechtmässigen Aufenthalt in der Schweiz nachweisen konnte.
A.b. Am 14./16. Mai 2019 reichten B._ und A._ ein erneutes Gesuch um Vorbereitung der Eheschliessung ein. Im Laufe dieses Verfahrens setzte das Zivilstandsamt ihnen eine Frist von 60 Tagen an, um den rechtmässigen Aufenthalt von A._ nachzuweisen.
Mit Verfügung vom 23. Mai 2019 wies das Migrationsamt des Kantons Zürich das Gesuch von A._ um Erteilung einer Kurzaufenthaltsbewilligung bzw. um Duldung des Aufenthalts zwecks Vorbereitung der Eheschliessung ab. Gegen diesen Entschied erhob A._ Rekurs bei der Sicherheitsdirektion des Kantons Zürich.
Am 3. Juli 2019 ersuchten B._ und A._ das Zivilstandsamt um Abnahme bzw. Erstreckung der Frist zum Nachweis des rechtmässigen Aufenthalts von A._. Mit Verfügung vom 30. Juli 2019 wies das Zivilstandsamt dieses Gesuch ab und verweigerte unter Hinweis auf den fehlenden rechtmässigen Aufenthalt von A._ die Fortsetzung des Ehevorbereitungsverfahrens.
B.
B.a. Das Gemeindeamt des Kantons Zürich wies das dagegen von B._ und A._ erhobene Rechtsmittel mit Verfügung vom 26. November 2019 ebenso ab, wie deren Gesuch um unentgeltliche Rechtspflege und Verbeiständung.
B.b. Soweit die unentgeltliche Rechtspflege und Verbeiständung betreffend erhoben B._ und A._ hiergegen Beschwerde beim Verwaltungsgericht des Kantons Zürich. Dieses wies das Rechtsmittel mit Urteil vom 28. Mai 2020 (eröffnet am 16. Juni 2020) unter Verweigerung der unentgeltlichen Rechtspflege und Verbeiständung im Beschwerdeverfahren ab.
C.
B._ und A._ gelangen mit Beschwerde in Zivilsachen vom 17. August 2020 ans Bundesgericht und beantragen unter Kostenfolge, die Angelegenheit sei unter Aufhebung des Urteils vom 28. Mai 2020 an das Verwaltungsgericht zurückzuweisen. Ausserdem ersuchen sie für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege und Verbeiständung.
Das Bundesgericht hat die Akten des vorinstanzlichen Verfahrens, indes keine Vernehmlassungen eingeholt.

Erwägungen:
1.
1.1. Fristgerecht (Art. 100 Abs. 1 und Art. 46 Abs. 1 Bst. b BGG) angefochten ist der Entscheid einer letzten kantonalen Instanz (<ref-law>), die auf Rechtsmittel hin über die unentgeltliche Rechtspflege in einem unterinstanzlichen kantonalen Beschwerdeverfahren betreffend die Vorbereitung einer Eheschliessung (<ref-law>) entschieden hat. Da das Ehevorbereitungsverfahren zwischenzeitlich abgeschlossen ist (vgl. vorne Bst. B), handelt es sich beim Entscheid über die unentgeltliche Rechtspflege um einen Endentscheid nach <ref-law> (Urteil 5A_456/2020 vom 7. Oktober 2020 E. 1.2). Als Nebenpunkt des Entscheids über das Verfahren auf Vorbereitung der Ehe (vgl. Urteil 5A_174/2016 vom 26. Mai 2016 E. 1) betrifft der angefochtene Entscheid wie dieser eine nicht vermögensrechtliche öffentlich-rechtliche Angelegenheit in unmittelbarem Zusammenhang mit dem Zivilrecht nach Art. 72 Abs. 2 Bst. b Ziff. 2 BGG (Urteile 5A_1041/2018 vom 9. Mai 2019 E. 1; 5A_764/2018 vom 28. Dezember 2018 E. 1). Damit ist die Beschwerde in Zivilsachen das zutreffende Rechtsmittel. Die Beschwerdeführer sind nach <ref-law> zur Beschwerde berechtigt, auf die einzutreten ist.
1.2. Die Beschwerde an das Bundesgericht ist ein reformatorisches Rechtsmittel (<ref-law>). Die beschwerdeführende Partei muss deshalb grundsätzlich einen Antrag in der Sache stellen, das heisst angeben, welche Punkte des kantonalen Entscheids sie anficht und inwiefern das Bundesgericht den angefochtenen Entscheid abändern soll. Rechtsbegehren, die eine Geldsumme zum Gegenstand haben, sind zu beziffern (<ref-ruling> E. 1.2; <ref-ruling> E. 3). Ausnahmsweise reicht ein Rückweisungsantrag aus, wenn das Bundesgericht im Falle einer Gutheissung in der Sache naturgemäss nicht selbst entscheiden könnte (<ref-ruling> E. 1.3).
Die Beschwerdeführer ersuchen einzig um Aufhebung des angefochtenen Urteils und Rückweisung der Sache an die Vorinstanz. Entgegen der sie auch insoweit treffenden Begründungspflicht (<ref-law>) äussern sie sich nicht dazu, weshalb dieser Antrag ausreichend sein sollte. Indes hat die Vorinstanz das streitbetroffene Gesuch allein zufolge der Aussichtslosigkeit der in der Hauptsache erhobenen Beschwerde abgewiesen und sich nicht zu den weiteren Voraussetzungen der unentgeltlichen Rechtspflege und gegebenenfalls zur Höhe des Honorars der unentgeltlichen Rechtsvertretung geäussert. Das Bundesgericht könnte daher offensichtlich nicht selbst in der Sache entscheiden, weshalb der rein kassatorische Antrag ausnahmsweise ausreicht (vgl. Urteil 5A_455/2020 vom 1. September 2020 E. 2).
2.
2.1. Die Vorinstanz entschied nach Massgabe von § 16 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 (VRG/ZH; LS 175.2) über das Gesuch der Beschwerdeführer um unentgeltliche Rechtspflege, was unbestritten geblieben ist (vgl. <ref-law>; Art. 89 Abs. 1 der Zivilstandsverordnung [ZStV; SR 211.112.2]; § 4 VRG/ZH; Urteil 5A_764/2018 vom 28. Dezember 2018 E. 6.1). Die Anwendung kantonalen Rechts kann das Bundesgericht namentlich auf die Verletzung von verfassungsmässigen Rechten hin überprüfen, wobei das strenge Rügeprinzip nach <ref-law> zur Anwendung gelangt (<ref-ruling> E. 6.1; <ref-ruling> E. 2.3). Das Bundesgericht prüft daher nur klar und detailliert erhobene und, soweit möglich, belegte Rügen, während es auf ungenügend substanziierte Rügen und rein appellatorische Kritik am Sachverhalt nicht eintritt (<ref-ruling> E. 2.4; <ref-ruling> E. 5.4).
2.2. Die Beschwerdeführer rügen vor Bundesgericht ausschliesslich eine Verletzung des Anspruchs auf unentgeltliche Rechtspflege nach <ref-law> und machen nicht geltend, dass die von der Vorinstanz zur Anwendung gebrachte kantonale Bestimmung über die verfassungsrechtliche Minimalgarantie hinausgehen würde. Auch sind sie nicht der Ansicht, das kantonale Recht sei willkürlich angewandt worden. Entsprechend ist der angefochtene Entscheid auf seine Vereinbarkeit mit der Verfassungsbestimmung hin zu prüfen (vgl. zu § 16 VRG/ZH <ref-ruling> E. 2.3; Urteile 2C_539/2018 vom 5. Oktober 2018 E. 3; 5A_790/2014 vom 5. Mai 2015 E. 3.1).
3.
3.1. Gemäss <ref-law> hat jede Person, die nicht über die erforderlichen Mittel verfügt, Anspruch auf unentgeltliche Rechtspflege, wenn ihr Rechtsbegehren nicht aussichtslos erscheint. Soweit es zur Wahrung ihrer Rechte notwendig ist, hat sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand. Vor Bundesgericht ist allein strittig, ob das Verwaltungsgericht das Gesuch der Beschwerdeführer um unentgeltliche Rechtspflege im Verfahren vor dem Gemeindeamt ohne Verfassungsverletzung als aussichtslos einstufen konnte.
Praxisgemäss sind Prozessbegehren als aussichtslos anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können. Von Aussichtslosigkeit darf hingegen nicht gesprochen werden, wenn Gewinnaussichten und Verlustgefahren sich ungefähr die Waage halten oder jene nur wenig geringer sind als diese. Massgebend ist, ob eine Partei, die über die nötigen Mittel verfügt, sich bei vernünftiger Überlegung zu einem Prozess entschliessen würde. Eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet. Ob im Einzelfall genügende Erfolgsaussichten bestehen, beurteilt sich aufgrund einer vorläufigen und summarischen Prüfung der Prozessaussichten, wobei die Verhältnisse im Zeitpunkt der Einreichung des Gesuchs massgebend sind (<ref-ruling> E. 5.1; <ref-ruling> E. 2.2).
3.2. Es ist unbestritten, dass die Beschwerdeführer im Verfahren vor dem Zivilstandsamt innert der ihnen angesetzten Frist von 60 Tagen den rechtmässigen Aufenthalt des Beschwerdeführers in der Schweiz nicht nachweisen konnten. Dies vor dem Hintergrund, dass deren Gesuch um Erteilung einer Kurzaufenthaltsbewilligung zwecks Heirat erstinstanzlich abgewiesen wurde (vgl. vorne Bst. A.b). Das Verwaltungsgericht erachtete die Frist von 60 Tagen als zur Erbringung des verlangten Nachweises ausreichend. Die Behörden seien auch nicht gehalten gewesen, diese zu verlängern. Eine Fristerstreckung könne zwar geboten sein, um den erstmaligen Entschied der Ausländerbehörden über eine Aufenthaltsbewilligung zwecks Eheschliessung abzuwarten. Ein Rechtsmittelverfahren über die Aufenthaltsbewilligung - ein solches ist hier hängig (vgl. vorne Bst. A.b) - vermöge eine Erstreckung der Frist aber nicht zu rechtfertigen. Entsprechend habe das Ehevorbereitungsverfahren mangels Nachweises des rechtmässigen Aufenthalts nicht fortgesetzt werden können. Die Beschwerdeführer könnten jederzeit ein neues Gesuch um Eheschliessung stellen, womit ihnen auch kein Nachteil erwachse. Demnach sei der gegen den Entscheid des Zivilstandsamtes gerichtete Rekurs von Anfang an aussichtslos gewesen und habe das Gesuch um unentgeltliche Rechtspflege ohne Rechtsverletzung abgewiesen werden können.
Die Beschwerdeführer sind der Ansicht, dass die Frist von 60 Tagen mit Blick auf die massgebenden Bestimmungen und vor dem Hintergrund, dass diese der Koordination der Entscheide der Zivil- und Ausländerbehörden dienten, bis zum Abschluss des ausländerrechtlichen Verfahrens zu verlängern gewesen wäre. Angesprochen sei dabei nicht nur das erstinstanzliche Verfahren, sondern auch ein allfälliges Rechtsmittelverfahren. Erst nach dessen Abschluss sei der Aufenthaltsstatus geklärt. Die Klärung dieses Status sei aber gemäss richtigem Verständnis der einschlägigen Weisungen des Eidgenössischen Amts für Zivilstandswesen (EAZW) Grund für eine Fristverlängerung. Auch müsse der betroffenen Person genügend Zeit zum Nachweis eingeräumt werden, dass mit der Heirat nicht das Ausländerrecht umgangen werden solle. Vorliegend sei es nicht von den Beschwerdeführern zu vertreten, dass der Beschwerdeführer den nötigen Nachweis nicht innert Frist habe erbringen können. Immerhin habe er vor Hängigkeit des Ehevorbereitungsverfahrens um Erteilung der Aufenthaltsbewilligung nachgesucht. Zu beachten sei auch, dass der Anspruch auf Eheschliessung grundrechtlich geschützt sei. Die Beschwerde ans Gemeindeamt sei daher keinesfalls aussichtslos gewesen.
3.3. Die Ehe wird nach dem Vorbereitungsverfahren vor der Zivilstandsbeamtin oder dem Zivilstandsbeamten geschlossen (<ref-law>). Verlobte, die nicht Schweizerbürgerinnen oder Schweizerbürger sind, müssen während des Vorbereitungsverfahrens ihren rechtmässigen Aufenthalt in der Schweiz nachweisen (<ref-law>; vgl. auch Art. 66 Abs. 2 Bst. e ZStV). Sind die Ehevoraussetzungen nicht erfüllt oder bleiben erhebliche Zweifel bestehen, so verweigert das Zivilstandsamt die Trauung (Art. 67 Abs. 3 ZStV). Das Zivilstandsamt kann nicht vorfrageweise über die Rechtmässigkeit des Aufenthalts der heiratswilligen Personen befinden. Kann der rechtmässige Aufenthalt nicht nachgewiesen werden, hat es diese daher an die zuständigen (Ausländer-) Behörden zu verweisen, damit der notwendige Nachweis beschafft werden kann. Hierzu ist eine angemessene Frist anzusetzen, wobei eine Dauer von 60 Tagen rechtsprechungsgemäss ausreichend ist (<ref-ruling> E. 5; Urteile 5A_743/2013 vom 27. November 2013 E. 5.2; 5A_612/2012 vom 19. November 2012 E. 6; vgl. auch die Weisungen Nr. 10.11.01.02 des EAZW vom 1. Januar 2011, Ziff. 2.2).
Diese Rechtsprechung steht vor dem Hintergrund einer konventions- und verfassungskonformen Auslegung von <ref-law>. Namentlich das von den Beschwerdeführern angerufene Recht auf Eheschliessung (Art. 12 EMRK; <ref-law>), indes auch das Verbot des überspitzten Formalismus (Art. 6 Ziff. 1 EMRK; <ref-law>) sowie der Grundsatz der Verhältnismässigkeit (<ref-law>) verlangen, dass auch eine sich unrechtmässig in der Schweiz aufhaltende Person die Ehe eingehen kann, ohne das Land verlassen zu müssen. Es ist ihr im Vorbereitungsverfahren daher (im Sinne einer Ausnahme; vgl. <ref-law> analog [SR 142.20]) die genannte Frist anzusetzen, um bei der zuständigen Behörden ihren Aufenthaltsstatus zu regeln, womit ihr die Eheschliessung in der Schweiz ermöglicht wird (<ref-ruling> E. 2-4; MONTINI/GRAF-GAISER, in: Basler Kommentar, Zivilgesetzbuch I, 6. Aufl. 2018, N. 6 zu <ref-law>, vgl. auch <ref-ruling> E. 3.5-3.7).
3.4. Gemäss der Rechtsprechung ist eine First von 60 Tagen zum Nachweis des rechtmässigen Aufenthalts nach <ref-law> namentlich auch dann ausreichend, wenn die Ausländerbehörde vor Anhebung des Ehevorbereitsungsverfahrens nicht um die Erteilung einer Aufenthaltsbedingung angegangen worden war (<ref-ruling> E. 5). Erfasst sind mithin auch Fälle, in denen - anders als hier - innert der angesetzten First das gesamte Verfahren vor der Ausländerbehörde durchlaufen werden muss. Das Vorbringen der Beschwerdeführer, es müsse die streitbetroffene Frist in jedem Fall einem allfälligen längerdauernden ausländerrechtlichen Rechtsmittelverfahren angepasst werden, überzeugt vor diesem Hintergrund nicht. Weiter rufen die Beschwerdeführer keine besonderen Gründe an, welche im konkreten Fall eine anderweitige Beurteilung notwendig machen würde. Ihnen helfen insoweit auch die vorgetragenen Konventions- und Vefassungsbezüge nicht weiter, welche in den genannten Entscheiden bereits berücksichtigt sind. Vor diesem Hintergrund und angesichts des Umstands, dass bloss eine summarische Prüfung der Prozessaussichten vorzunehmen war (vgl. E. 3.1 hiervor), konnte die Vorinstanz die beim Gemeindeamt erhobene Beschwerde ohne Verfassungsverletzung als aussichtslos einstufen. Hieran ändern, wie nachfolgend aufzuzeigen ist, auch die weiteren Vorbringen der Beschwerdeführer nichts.
3.5. Ohne Grund machen die Beschwerdeführer geltend, die vorzitierte Rechtsprechung fände keine Anwendung: Anders als sie meinen, ist nicht entscheidend, ob die betroffene Person von der ihr eingeräumten Frist tatsächlich Gebrauch macht oder nicht. Ebenso wenig kommt es darauf an, ob die Beschwerdeführer ein Verschulden trifft. Ausschlaggebend ist vielmehr, dass ihnen die Möglichkeit eingeräumt wurde, bei der zuständigen Behörde den Nachweis des rechtmässigen Aufenthalts zu beschaffen. Diese Möglichkeit haben sie erhalten (vgl. vorne Bst. A.b). Sodann ist nicht ersichtlich, weshalb die Vorinstanz sich nicht hätte auf Entscheide des Bundesgerichts berufen dürfen, die nicht in der amtlichen Sammlung publiziert sind. Diese Entscheide sind der Öffentlichkeit ebenfalls zugänglich (<ref-law>; Art. 59 des Reglements vom 20. November 2006 für das Bundesgericht [BGerR; SR 173.110.131]) und werden (teilweise) auch in den von den Beschwerdeführern selbst angerufenen Weisungen des EAZW erwähnt (vgl. Weisungen, Ziffer 2.2 Fn. 28). Nach dem Ausgeführten ist auch die Einschätzung der Beschwerdeführer zu relativieren, es habe sich im Verfahren vor dem Gemeindeamt eine noch ungeklärte Rechtsfrage gestellt.
3.6. Nicht entscheidend erscheint sodann, ob den Beschwerdeführern durch die Nichtverlängerung der Frist und in der Folge die Nichtfortsetzung des Ehevorbereitungsverfahrens gewisse (tatsächliche) Nachteile entstehen. Den Auswirkungen der fraglichen Regelung auf die betroffenen Personen ist vielmehr, ebenso wie den an der Regelung bestehenden öffentlichen Interessen, grundsätzlich bereits im Rahmen der vorgenannten Rechtsprechung Rechnung getragen worden, welche die Verhältnismässigkeit der Massnahme berücksichtigt hat (vgl. vorne E. 3.3; zur diesbezüglichen Interessenabwägung vgl. etwa <ref-ruling> E. 3.1). Im zitierten Leitentscheid <ref-ruling> wurde insbesondere auch bedacht, dass eine (Kurz-) Aufenthaltsbewilligung zum Zweck des Eheschlusses in der Regel nur erteilt wird, wenn dieser kurz bevorsteht, worauf die Hängigkeit des Ehevorbereitungsverfahrens einen Einfluss haben kann (E. 2.1; vgl. zu dieser Problematik Urteil 2C_827/2019 vom 17. Januar 2020 E. 3). Es ist nicht ersichtlich oder dargetan, aus welchem (besonderen) Grund vorliegend hierauf zurückzukommen wäre. Die Beschwerdeführer können aus diesen Umständen folglich nichts für sich ableiten.
3.7. Damit erweist sich die Beschwerde als unbegründet. Nicht bzw. nur unter der nicht verwirklichten Prämisse der Begründetheit der Beschwerde angefochten ist sodann die Verweigerung der unentgeltlichen Rechtspflege im Verfahren vor der Vorinstanz. Hierauf ist folglich nicht weiter einzugehen.
4.
Nach dem Ausgeführten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten grundsätzlich den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>) und haben sie keinen Anspruch auf Ersatz ihrer Parteikosten (Art. 68 Abs. 1 und 2 BGG). Auch dem Gemeinwesen ist keine Parteientschädigung auszurichten (<ref-law>).
Die Beschwerdeführer ersuchen für das Verfahren vor Bundesgericht allerdings um unentgeltliche Rechtspflege und Verbeiständung. Dieses Gesuch ist gutzuheissen, da die entsprechenden Voraussetzungen erfüllt sind (Art. 64 Abs. 1 und 2 BGG). Die Gerichtskosten sind daher auf die Bundesgerichtskasse zu nehmen, den Beschwerdeführern ist ihr Vertreter als unengeltlicher Rechtsbeistand beizuordnen und dieser ist aus der Bundesgerichtskasse zu entschädigen. Die Beschwerdeführer werden darauf hingewiesen, dass sie der Bundesgerichtskstasse Ersatz zu leisten haben, wenn sie dazu später in der Lage sind (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch der Beschwerdeführer um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren wird gutgeheissen und ihnen wird Rechtsanwalt Sven Gretler als unengetlicher Rechtsvertreter beigeordnet.
3.
Die Gerichtskosten von Fr. 1'500.-- werden den Beschwerdeführern auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Rechtsanwalt Gretler wird aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
5.
Dieses Urteil wird den Parteien, dem Zivilstandsamt der Stadt Zürich, und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, Einzelrichter, schriftlich mitgeteilt.
Lausanne, 25. Februar 2021
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Sieber