Sachverhalt:
A.
A.a. A._, dessen Identität noch nicht zweifelsfrei festgestellt werden konnte, reiste am 10. Oktober 2018 in die Schweiz ein und stellte ein Asylgesuch.
Mit Strafbefehl vom 1. Februar 2019 verurteile die Staatsanwaltschaft des Kantons Luzern A._ wegen mehrfachen Diebstahls zu einer bedingt ausgesprochenen Geldstrafe von 30 Tagessätzen zu je Fr. 30.-- und einer Busse von Fr. 200.--.
Am 14. März 2019 grenzte das Migrationsamt des Kantons Zürich A._ für zwei Jahre aus den Gebieten der Stadt Zürich und der Gemeinde Oetwil am See aus. Diese Ausgrenzung missachtete A._.
Das Staatssekretariat für Migration (SEM) wies das Asylgesuch A._s am 4. April 2019 ab und wies ihn unter Ansetzung einer Ausreisefrist bis zum 23. April 2019 aus der Schweiz weg.
Ab dem 15. April 2019 galt A._ als verschwunden.
A.b. Am 26. April 2019 wurde A._ in Ausschaffungshaft genommen. Das Zwangsmassnahmengericht (Bezirksgericht Zürich) bestätigte am 27. April 2019 die vom Migrationsamt des Kantons Zürich verfügte Anordnung der Ausschaffungshaft und verlängerte diese Haft in der Folge mehrfach. Eine gegen die Bestätigung der Verlängerung vom 20. Januar 2020 erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 19. März 2020 ab.
A.c. A._ stellte (ebenfalls) am 19. März 2020 ein Haftentlassungsgesuch. Dieses wurde vom Zwangsmassnahmengericht am 1. April 2020 abgewiesen. Gleichentags ist das SEM auf ein Gesuch A._s um Anerkennung der Staatenlosigkeit nicht eingetreten.
B.
Das Verwaltungsgericht des Kantons Zürich wies mit Urteil vom 7. Mai 2020 eine gegen das Urteil des Zwangsmassnahmengerichts vom 1. April 2020 erhobene Beschwerde A._s ab. Die Gerichtskosten wurden dabei A._ auferlegt, doch wegen offensichtlicher Unerhältlichkeit abgeschrieben und das Gesuch um unentgeltliche Rechtspflege wurde als gegenstandslos erklärt. Eine Parteientschädigung sprach das Verwaltungsgericht nicht zu. Schliesslich bestellte es Rechtsanwältin Lea Hungerbühler als unentgeltliche Rechtsvertreterin A._s und richtete ihr aus der Gerichtskasse eine Entschädigung aus.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 20. Mai 2020 beantragt A._, unter Aufhebung des Urteils des Verwaltungsgerichts des Kantons Zürich vom 7. Mai 2020 sei er unverzüglich aus der Ausschaffungshaft zu entlassen und sei eventualiter die Angelegenheit zu neuer Entscheidung an dieses Gericht zurückzuweisen. A._ ersucht ferner um unentgeltliche Prozessführung bzw. Kostenbefreiung sowie unentgeltliche Verbeiständung.
Der Abteilungspräsident wies am 22. Mai 2020 ein mit der Beschwerde gestelltes Gesuch von A._, ihn im Rahmen einer vorsorglichen Massnahme mit sofortiger Wirkung aus der Ausschaffungshaft zu entlassen, ab. Auf die Erhebung eines Kostenvorschusses wurde verzichtet.
Das Migrationsamt des Kantons Zürich und das Bezirksgericht Zürich verzichten auf Vernehmlassung. Das Verwaltungsgericht das Kantons Zürich beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten ist. Das Staatssekretariat für Migration (SEM) lässt sich mit Schreiben vom 2. Juni 2020 vernehmen.

Erwägungen:
1.
1.1. Die frist- (<ref-law>) und formgerecht (<ref-law>) eingereichte Beschwerde betrifft eine Angelegenheit des öffentlichen Rechts (<ref-law>) und richtet sich gegen den kantonal letztinstanzlichen (<ref-law>), verfahrensabschliessenden Entscheid (<ref-law>) eines oberen kantonalen Gerichts (<ref-law>). Der Anordnung ausländerrechtlicher Administrativhaft kommt aufgrund ihres schweren Eingriffs in die persönliche Freiheit eigenständiger Charakter zu; sie erscheint nicht als bloss untergeordnete Vollzugsmassnahme zur Wegweisung. Die Beschwerde ist somit auch unter dem Blickwinkel von <ref-law> zulässig (vgl. <ref-ruling> E. 1.1.3 S. 139 f.; <ref-ruling> E. 1 S. 24 f.; <ref-ruling> E. 5.5 S. 101).
1.2.
1.2.1. Zur Beschwerde ist berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit zur Teilnahme erhalten hat, durch den angefochtenen Entscheid besonders berührt ist und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (<ref-law>). Ob diese Voraussetzungen gegeben sind, prüft das Bundesgericht von Amtes wegen. Das schutzwürdige Interesse muss grundsätzlich nicht nur bei der Beschwerdeeinreichung, sondern auch noch im Zeitpunkt der Urteilsfällung aktuell und praktisch sein. Fällt das schutzwürdige Interesse im Laufe des Verfahrens dahin, wird die Sache als erledigt erklärt; fehlte es schon bei der Beschwerdeeinreichung, ist auf die Eingabe nicht einzutreten (BGE <ref-ruling> E. 1.3 mit Hinweisen). Das Bundesgericht verzichtet ausnahmsweise auf das Erfordernis des aktuellen praktischen Interesses, wenn sich die aufgeworfenen Fragen unter gleichen oder ähnlichen Umständen jederzeit wieder stellen können, eine rechtzeitige Überprüfung im Einzelfall kaum je möglich wäre und die Beantwortung wegen ihrer grundsätzlichen Bedeutung im öffentlichen Interesse liegt (<ref-ruling> E. 1.1 S. 208, mit Hinweisen).
1.2.2. Die Vorinstanz führt aus, dass die Haft zuletzt am 20. Januar 2020 bis am 25. April 2020 verlängert worden sei (E. 2 des angefochtenen Urteils). Dies wirft die Frage auf, ob sich der Beschwerdeführer aktuell überhaupt noch in Haft befindet und an der Aufhebung des angefochtenen Urteils noch ein aktuelles und praktisches Interesse hat. Diese Frage betrifft eine Prozessvoraussetzung, sodass das Bundesgericht insoweit auch Tatsachen und Beweismittel berücksichtigen kann, die neu sind oder sich aus anderen Gründen nicht aus dem angefochtenen Urteil ergeben (vgl. <ref-ruling> E. 3.2.1 S. 616; vgl. auch <ref-ruling> E. 5.2 S. 428). Aus den Akten ergibt sich, dass das Zwangsmassnahmengericht Zürich die Ausschaffungshaft zuletzt mit Urteil vom 22. April 2020 bis zum 22. Juli 2020 verlängert hat. Folglich befindet sich der Beschwerdeführer weiterhin in Ausschaffungshaft. Er hat ein aktuelles und praktisches Interesse an der Aufhebung des angefochtenen Urteils. Auf seine Beschwerde ist einzutreten.
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann namentlich die Verletzung von Bundes- und Völkerrecht gerügt werden (<ref-law>). Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (<ref-law>), grundsätzlich nur die geltend gemachten Vorbringen, sofern allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 f. mit Hinweis). Die Verletzung von Grundrechten untersucht das Bundesgericht in jedem Fall nur insoweit, als eine solche Rüge in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; vgl. <ref-ruling> E. 3 S. 415; <ref-ruling> E. 2.2 S. 232).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Eine Berichtigung oder Ergänzung der vorinstanzlichen Sachverhaltsfeststellungen ist von Amtes wegen (<ref-law>) oder auf Rüge hin (<ref-law>) möglich. Von den tatsächlichen Grundlagen des vorinstanzlichen Urteils weicht das Bundesgericht jedoch nur ab, wenn diese offensichtlich unrichtig sind oder sie auf einer Rechtsverletzung im Sinne von <ref-law> beruhen und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (Art. 97 Abs. 1, <ref-law>; <ref-ruling> E. 1.3.1 S. 17 f.).
3.
Die Vorinstanz lehnte es ab, den Beschwerdeführer aus der Haft zu entlassen. Zwar seien Rückführungen aufgrund des Coronavirus COVID-19 aktuell nicht möglich und es sei ungewiss, ob sich die Lage in absehbarer Zeit wieder normalisieren werde und einzelne Flüge stattfinden können. Indes könne heute nicht gesagt werden, dass es sich dabei nur um eine rein theoretische Möglichkeit handle.
Der Beschwerdeführer ist der Ansicht, dass die Rückführung aufgrund der COVID-19-Pandemie nicht mehr absehbar sei und er deshalb gestützt auf <ref-law> aus der Haft entlassen werden müsse.
3.1. Ist der Vollzug der Wegweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar (<ref-law>), lässt sich die Ausschaffungshaft nicht mehr mit einem hängigen Wegweisungsverfahren rechtfertigen; sie verstösst zugleich gegen Art. 5 Ziff. 1 lit. f EMRK (vgl. <ref-ruling> E. 4.1.1 S. 59 f.; <ref-ruling> E. 3 S. 152 f.; Urteile 2C_312/2020 vom 9. Juni 2020 E. 2.1; 2C_268/2018 vom 11. April 2018 E. 2.3.1). Wie es sich mit der Durchführbarkeit des Wegweisungsvollzugs im Einzelnen verhält, bildet Gegenstand einer nach pflichtgemässem Ermessen vorzunehmenden Prognose. Massgebend ist, ob der Wegweisungsvollzug mit hinreichender Wahrscheinlichkeit innert absehbarer Zeit möglich erscheint oder nicht. Die Haft verstösst gegen <ref-law> und ist zugleich unverhältnismässig, wenn triftige Gründe dafür sprechen, dass die Wegweisung innert vernünftiger Frist nicht vollzogen werden kann (vgl. <ref-ruling> E. 4.1.3 S. 61 mit Hinweisen; Urteile 2C_312/2020 vom 9. Juni 2020 E. 2.1; 2C_268/2018 vom 11. April 2018 E. 2.3.1). Unter dem Blickwinkel von <ref-law> ist die Haft indes nur aufzuheben, wenn keine oder bloss eine höchst unwahrscheinliche, rein theoretische Möglichkeit besteht, dass die Wegweisung vollzogen werden kann, nicht indessen bei einer ernsthaften, wenn auch allenfalls (noch) geringen Aussicht hierauf (vgl. <ref-ruling> E. 4.1.3 S. 61). Unter Vorbehalt einer Beeinträchtigung der öffentlichen Ordnung durch die betroffene Person ist die Frage nach der Durchführbarkeit des Wegweisungsvollzugs im Sinne von <ref-law> nicht notwendigerweise im Hinblick auf die maximale Haftdauer, sondern vielmehr auf einen den gesamten Umständen des konkreten Falls angemessenen Zeitraum zu beurteilen (vgl. <ref-ruling> E. 4.1.3 S. 61; <ref-ruling> E. 3b/bb S. 223; Urteile 2C_312/2020 vom 9. Juni 2020 E. 2.1; 2C_268/2018 vom 11. April 2018 E. 2.3.1).
3.2. Aus dem angefochtenen Urteil ergibt sich nicht, welchen Zeithorizont die Vorinstanz ihrer Beurteilung der Absehbarkeit im Fall des Beschwerdeführers zugrunde gelegt hat. Falls die Vorinstanz aufgrund der strafrechtlichen Verurteilung des Beschwerdeführers ausnahmsweise auf die maximal zulässige Haftdauer hätte abstellen dürfen (vgl. oben E. 3.1), hätte sie ihrer Prognose einen Zeitraum von rund sechs Monaten zugrunde legen müssen.
3.3. Selbst wenn der Beurteilung ein derart oder zumindest ein ähnlich langer Zeitraum zugrundegelegt werden durfte, fehlte es vorliegend an der Absehbarkeit des Vollzugs der Wegweisung.
3.3.1. Ist der zwangsweise Vollzug der Wegweisung in ein Land aktuell ausgeschlossen, lässt er sich nur als innert absehbarer Frist möglich und damit als durchführbar bezeichnen, wenn dem Haftrichter dafür hinreichend konkrete Hinweise insbesondere seitens des SEM vorliegen (Urteile 2C_312/2020 vom 9. Juni 2020 E. 2.3.1; 2C_386/2010 vom 1. Juni 2010 E. 6). Andernfalls fehlt es an der ernsthaften Aussicht auf den Vollzug der Wegweisung, die das Bundesgericht praxisgemäss voraussetzt (vgl. oben E. 3.1).
3.3.2. Die Identität des Beschwerdeführers ist ungeklärt. Die Behörden vermuten, dass er entweder aus Algerien, aus dem Libanon oder aus Palästina stammt. Ob der Vollzug der Wegweisung undurchführbar im Sinne von <ref-law> ist, hängt also davon ab, ob Rückführungen in diese Länder mit hinreichender Wahrscheinlichkeit als innert absehbarer Zeit möglich erscheinen (vgl. Urteil 2C_312/2020 vom 9. Juni 2020 E. 2.3.1). Die Vorinstanz nimmt keinen Bezug auf die konkrete Situation in diesen Ländern, sondern geht global davon aus, dass Rückführungen absehbar blieben, auch wenn sie aktuell wegen der COVID-19-Pandemie unmöglich seien. Der Vorinstanz lagen also keinerlei Hinweise dafür vor, wann zwangsweise Rückführungen nach Algerien, in den Libanon und nach Palästina (wieder) möglich sein würden. Auch aus der Stellungnahme des SEM ergeben sich keine solche Hinweise. Wie das Bundesgericht bereits in BGE <ref-ruling> für eine hinsichtlich der ungewissen Dauer des Vollzugshindernisses vergleichbare Konstellation - Luftangriffe der NATO in Jugoslawien - entschieden hat, reicht die vage Möglichkeit, dass das Vollzugshindernis in absehbarer Zeit entfallen könnte, jedoch nicht aus, um die Ausschaffungshaft aufrecht zu erhalten (vgl. BGE <ref-ruling> E. 3b/bb S. 223 f.).
3.3.3. Nach dem Gesagten bestanden im Zeitpunkt des angefochtenen Urteils keine ernsthaften Aussichten darauf, dass der Vollzug der Wegweisung des Beschwerdeführers innert absehbarer Frist durchgeführt werden könnte. Richtigerweise hätte die Vorinstanz daher gestützt auf <ref-law> die unverzügliche Entlassung des Beschwerdeführers aus der Ausschaffungshaft anordnen müssen. Ihr gegenteiliges Urteil verletzt Bundesrecht und Art. 5 Ziff. 1 lit. f EMRK.
4.
Da die Ausschaffungshaft bereits nach <ref-law> nicht länger aufrecht erhalten werden darf, braucht nicht geprüft zu werden, ob den Behörden eine Verletzung des Beschleunigungsgebots (<ref-law>; <ref-law>) vorzuwerfen ist.
5.
5.1. Die Beschwerde erweist sich als begründet und ist gutzuheissen. Das angefochtene Urteil ist aufzuheben. Der fortdauernden Inhaftierung fehlt die rechtliche Grundlage. Der Beschwerdeführer ist folglich unverzüglich aus der Haft zu entlassen (<ref-ruling> E. 5.5 S. 6).
5.2. Bei diesem Verfahrensausgang sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Zürich hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung (<ref-law>) wird mit Blick auf die genannten Kosten- und Entschädigungsfolgen gegenstandslos. Die Sache ist zur Neuregelung der Kosten- und Entschädigungsfolgen des vorangegangenen Verfahrens an die Vorinstanz zurückzuweisen (vgl. Art. 67 und 68 Abs. 5 BGG e contrario).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und das Urteil des Einzelrichters des Verwaltungsgerichts des Kantons Zürich vom 7. Mai 2020 aufgehoben. Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat der Rechtsvertreterin des Beschwerdeführers eine Parteientschädigung von Fr. 2'500.-- zu bezahlen.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, Einzelrichter, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 12. Juni 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Zünd
Der Gerichtsschreiber: Seiler