Sachverhalt:
A.
A._, ein 1989 geborener Staatsangehöriger Afghanistans, stellte am 17. Oktober 2015 in der Schweiz ein Asylgesuch. Mit Entscheid vom 12. September 2018 wies das Staatssekretariat für Migration das Gesuch ab. Eine hiergegen erhobene Beschwerde wurde vom Bundesverwaltungsgericht mit Entscheid vom 12. April 2019 wegen unbekannten Aufenthaltsortes von A._ als gegenstands los abgeschrieben.
Nach einem Aufenthalt in Frankreich befand sich A._ jedenfalls ab dem 10. Mai 2019 erneut in der Schweiz.
B.
Am 13. Mai 2019 verfügte das Migrationsamt des Kantons Zürich die Wegweisung von A._ und ordnete an, dass er in Ausschaffungshaft genommen werde. Das Zwangsmassnahmegericht (Bezirksgericht Zürich) bestätigte am 14. Mai 2019 die Ausschaffungshaft. In der Folge wurde diese Haft wiederholt verlängert, und zwar zuletzt mit Urteil des Zwangsmassnahmegerichts vom 2. Mai 2020 bis zum 4. August 2020.
Eine gegen das Urteil des Zwangsmassnahmegerichts vom 2. Mai 2020 erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 4. Juni 2020 ab.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. Juni 2020 beantragt A._,er sei unter Aufhebung des Urteils des Verwaltungsgerichts des Kantons Zürich vom 4. Juni 2020 unverzüglich aus der Ausschaffungshaft zu entlassen. Ferner beantragt A._, ein Antrag des Migrationsamtes des Kantons Zürich auf Verlängerung der Ausschaffungshaft sei abzuweisen. A._ ersucht ferner um Neuregelung der Kosten- und Entschädigungsfolgen der vorangegangenen Verfahren zulasten des Kantons Zürich sowie um unentgeltliche Prozessführung bzw. Kostenbefreiung sowie unentgeltliche Verbeiständung für das bundesgerichtliche Verfahren.
Das Migrationsamt des Kantons Zürich beantragt, die Beschwerde sei abzuweisen. Das Bezirksgericht Zürich und das Verwaltungsgericht des Kantons Zürich verzichten auf Vernehmlassung. Das Staatssekretariat für Migration reichte am 10. Juli 2020 aufforderungsgemäss einen Amtsbericht ein.

Erwägungen:
1.
1.1. Die frist- und formgerecht 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).
Der Beschwerdeführer, der am vorinstanzlichen Verfahren teilgenommen hat und mit seinen Anträgen unterlegen ist, ist zur Beschwerde berechtigt (<ref-law>).
1.2. Mit der Beschwerde wird unter anderem beantragt, ein Antrag des Beschwerdegegners 1 auf Verlängerung der Ausschaffungshaft sei abzuweisen. Eine Verlängerung der Ausschaffungshaft über den 4. August 2020 hinaus war jedoch weder Gegenstand des angefochtenen Urteils noch hätte die Vorinstanz über eine solche Haftverlängerung entscheiden müssen. Weil der Streitgegenstand im Laufe des Rechtsmittelverfahrens nur eingeschränkt, nicht aber ausgeweitet werden kann (<ref-ruling> E. 3.4.2 S. 365; <ref-ruling> E. 5 S. 174; <ref-ruling> E. 2 S. 31 f. mit Hinweisen), ist dementsprechend auf das Begehren, der Antrag des Beschwerdegegners 1 auf Verlängerung der Ausschaffungshaft sei abzuweisen, nicht einzutreten.
1.3. Mit der vorgenannten Einschränkung (E. 1.2) ist auf die Beschwerde 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. 2.2 S. 232; <ref-ruling> E. 3 S. 415).
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.
3.1. Der rechtskräftig weggewiesene Beschwerdeführer ist in der Vergangenheit schon einmal untergetaucht. Infolgedessen hat die Vorinstanz entsprechend der bundesgerichtlichen Rechtsprechung zutreffend angenommen, dass beim Beschwerdeführer Untertauchensgefahr besteht und damit ein Haftgrund im Sinne von Art. 76 Abs. 1 lit. b Ziff. 3 und 4 AIG (SR 142.20) gegeben ist (vgl. <ref-ruling> E. 3.1 S. 58 f.; <ref-ruling> E. 2a S. 50 f.; Urteil 2C_371/2020 vom 2. Juni 2020 E. 3.1).
3.2. 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).
In Frage steht vorliegend, ob der Vollzug der Wegweisung des Beschwerdeführers im Sinne von <ref-law> undurchführbar und die Ausschaffungshaft deshalb zu beenden ist.
3.2.1. Die Vorinstanz verneinte eine rechtserhebliche Undurchführbarkeit des Wegweisungsvollzuges. Sie hielt fest, die Identität des Beschwerdeführers sei geklärt und die afghanischen Behörden seien dazu bereit, ein "Laissez-Passer" des Eidgenössischen Justiz- und Polizeidepartements (EJPD) zu akzeptieren, wenn die afghanische Botschaft bis zum 23. April 2020 kein afghanisches "Laissez-Passer" ausstelle. Dies bedeute, dass ab dem 23. April 2020 ein Flug - wohl eine begleitete Rückführung - vorgesehen werden könne. Indessen sei die entsprechende Abmachung mit den afghanischen Behörden noch nicht praxiserprobt und habe ein durch das Migrationsamt in Auftrag gegebener Flug Mitte April 2020 aufgrund der Coronavirus COVID-19-Pandemie annulliert werden müssen.
3.2.2. Weiter erklärte die Vorinstanz, zwar seien zurzeit Prognosen darüber, ob sich die aufgrund des Coronavirus COVID-19-Pandemie bestehende Lage in Afghanistan und in der Schweiz in absehbarer Zeit wieder normalisieren wird, sehr schwierig. Indessen könne nicht gesagt werden, dass eine Rückführung nach Afghanistan eine rein theoretische Möglichkeit bilde. Selbst bei Mitberücksichtigung der erhöhten Ungewissheit aufgrund der Coronavirus COVID-19-Pandemie erscheine die Aufrechterhaltung der Ausschaffungshaft als verhältnismässig.
3.3. 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_323/2020 vom 18. Juni 2020 E. 5.4.2; 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 mit Blick 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_414/2020 vom 12. Juni 2020 E. 3.1; 2C_312/2020 vom 9. Juni 2020 E. 2.1; 2C_268/2018 vom 11. April 2018 E. 2.3.1). Abzustellen ist auf den Zeitpunkt des angefochtenen Entscheids; ob der zwangsweise Vollzug in ein Land innert absehbarer bzw. angemessener Frist möglich ist, ist aus der entsprechenden Optik zu beurteilen (Urteile 2C_510/2020 vom 7. Juli 2020 E. 3.2.2; 2C_323/2020 vom 18. Juni 2020 E. 5.4.3; 2C_386/2020 vom 9. Juni 2020 E. 4.2.2; vgl. ferner Urteil 2C_312/2020 vom 25. Mai 2020 E. 2.3.3).
3.4.
3.4.1. Ob der Vollzug der Wegweisung undurchführbar im Sinne von <ref-law> ist, hängt im vorliegenden Fall davon ab, ob eine Rückführung nach Afghanistan, dem Heimatstaat des Beschwerdeführers, mit hinreichender Wahrscheinlichkeit als innert absehbarer Zeit möglich erscheint.
3.4.2. Der Vorinstanz lagen keine konkreten Hinweise dafür vor, wann zwangsweise Rückführungen nach Afghanistan wieder möglich sein würden. Als solcher Hinweis lässt sich insbesondere nicht der im angefochtenen Urteil genannte Umstand werten, dass die Ausreiseorganisation Flughafen erklärte, dass die "Vollzugsmöglichkeiten Afghanistan" voraussichtlich im Juni 2020 definiert werden könnten. Die Vorinstanz beschränkte sich im Wesentlichen darauf, auf die sehr grossen Schwierigkeiten bei Prognosen zur weltweiten Entwicklung der Situation betreffend das Coronavirus COVID-19 hinzuweisen. Ihre Annahme, dass die Möglichkeit von Rückführungen nach Afghanistan mehr als eine rein theoretische Möglichkeit bildet, untermauert die Vorinstanz nicht näher.
3.4.3. Zwar bringt das kantonale Migrationsamt in seiner Vernehmlassung vom 6. Juli 2020 vor, gemäss den Akten sei der Flughafen in Kabul wieder offen und würden bereits wieder erste Flüge durchgeführt werden. Indessen legt das Migrationsamt nicht dar, aus welchen bereits im Zeitpunkt des Erlasses des angefochtenen Urteils zu den Akten genommenen Unterlagen konkrete Flugmöglichkeiten ersichtlich sein sollen. Da auf den Zeitpunkt des angefochtenen Entscheids abzustellen ist (E. 3.3 hiervor), kann aus dem Umstand, dass der Flugbetrieb nach Kabul nach diesem Zeitpunkt (allenfalls) wieder aufgenommen wurde, nicht abgeleitet werden, dass eine Rückführung des Beschwerdeführers im massgeblichen Sinne innert absehbarer Zeit möglich ist.
3.4.4. Auch dem vorliegenden Amtsbericht des Staatssekretariates für Migration vom 10. Juli 2020 lassen sich keine konkreten Hinweise darauf entnehmen, dass im massgebenden Zeitpunkt des Erlasses des angefochtenen Urteils vom 4. Juni 2020 mehr als eine rein theoretische Möglichkeit der Rückführung des Beschwerdeführers nach Afghanistan bestand:
Das Staatssekretariat für Migration führt aus, die für den 11. Mai 2020 vorgesehene Rückführung des Beschwerdeführers habe aufgrund der Coronavirus COVID-19-Pandemie annulliert werden müssen. In Übereinstimmung mit dem kantonalen Migrationsamt erklärt es sodann, zwischenzeitlich habe der Flugbetrieb wieder aufgenommen werden können. Nach der Darstellung des Staatssekretariats reiste dabei am 2. Juli 2020 eine erste Person selbständig aus der Schweiz nach Kabul. Es erscheint als bezeichnend, dass das Staatssekretariat weder behauptet, der Flugbetrieb nach Afghanistan sei vor dem Erlass des angefochtenen Urteils am 4. Juni 2020 wieder aufgenommen worden, noch erläutert, dass und weshalb bereits zu diesem (allein) massgebenden Zeitpunkt (E. 3.3 hiervor) die (tatsächlich anscheinend erst am 2. Juli 2020 eröffnete) Reisemöglichkeit infolge voraussehbarer Wiederaufnah me des Luftverkehrs absehbar war.
3.4.5. Bei dieser Sachlage muss davon ausgegangen werden, dass im Zeitpunkt des angefochtenen Urteils keine ernsthaften Aussichten darauf bestanden, dass der Vollzug der Wegweisung des Beschwerdeführers innert absehbarer Frist durchgeführt werden könnte. An diesem Schluss nichts zu ändern vermag der Umstand, dass vorliegend mit den Behörden Afghanistans eine Einigung getroffen werden konnte, mit welcher die Beschaffung der für die Rückführung erforderlichen Papiere sichergestellt ist. Denn massgebend erscheint allein, dass die tatsächlichen Reisemöglichkeiten im Zeitpunkt des angefochtenen Urteils nicht hinreichend absehbar waren.
In Erinnerung zu rufen ist in diesem Kontext nicht zuletzt, dass nach einem Entscheid des Bundesgerichts zu einer hinsichtlich der ungewissen Dauer des Vollzugshindernisses vergleichbaren Konstellation (Luftangriffe der NATO in Jugoslawien) die vage Möglichkeit, dass das Vollzugshindernis in absehbarer Zeit entfallen könnte, nicht ausreicht, um die Ausschaffungshaft aufrecht zu erhalten (vgl. BGE <ref-ruling> E. 3b/bb S. 223 f.).
3.5. Der Gesetzgeber hat in <ref-law> festgehalten, wie lange ein Betroffener zwecks Ausschaffung inhaftiert werden darf. Dies sind in einer ersten Phase maximal sechs Monate (<ref-law>). Nur wenn die inhaftierte Person nicht mit den zuständigen Behörden kooperiert oder sich die Übermittlung der für die Ausreise erforderlichen Unterlagen durch einen Nicht-Schengenstaat verzögert, kann die Haft um 12 Monate auf maximal 18 Monate verlängert werden (<ref-law>). Der Beschwerdeführer befand sich im Zeitpunkt des Erlasses des angefochtenen Urteils bereits rund 13 Monate in Ausschaffungshaft; den Umstand, dass seine Ausschaffung nicht vorangetrieben werden kann, haben derzeit jedoch weder er noch sein Heimatstaat zu verantworten. Auch aus diesem Grund ist seine Haft zu beenden. Dies schliesst nicht aus, dass bei einer grundlegenden Änderung der Pandemiesituation unter Berücksichtigung sämtlicher konkreter Umstände eine Wiederaufnahme der Ausschaffungshaft beim Beschwerdeführer möglich wird (vgl. <ref-ruling> E. 4.1.3; Urteil 2C_386/2020 vom 9. Juni 2020 E. 4.2.5).
4.
Nach dem Gesagten hätte die Vorinstanz richtigerweise mangels ernsthafter Aussichten darauf, dass der Vollzug der Wegweisung innert absehbarer Frist durchgeführt werden könnte, gestützt auf <ref-law> die unverzügliche Entlassung des Beschwerdeführers aus der Ausschaffungshaft anordnen müssen. Ihr gegenteiliges Urteil verletzt Bundesrecht und - wie der Beschwerdeführer zutreffend rügt - Art. 5 Ziff. 1 lit. f EMRK.
Soweit auf die Beschwerde einzutreten ist, ist diese somit gutzuheissen. Das angefochtene Urteil ist aufzuheben. Der Inhaftierung über den Zeitpunkt des angefochtenen Urteils hinaus fehlt die rechtliche Grundlage. Der Beschwerdeführer ist folglich unverzüglich aus der Haft zu entlassen (vgl. <ref-ruling> E. 5.5 S. 6).
5.
5.1. Im Umfang seines Obsiegens sind dem Beschwerdeführer keine Verfahrenskosten aufzuerlegen (vgl. <ref-law> e contrario) und hat der Kanton Zürich dem Beschwerdeführer eine reduzierte Parteientschädigung zu bezahlen (<ref-law>).
Soweit der Beschwerdeführer mit seinem Begehren, der Antrag des Migrationsamtes um Verlängerung der Ausschaffungshaft sei abzuweisen, nicht durchdringt und damit unterliegt (vgl. E. 1.2 hiervor), rechtfertigt es sich, auf die Erhebung von Gerichtskosten zu verzichten (vgl. <ref-law>).
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung (<ref-law>) wird unter diesen Umständen gegenstandslos.
5.2. Die Sache ist zur Neuregelung der Kosten- und Entschädigungsfolgen der vorangegangenen Verfahren an die Vorinstanz zurückzuweisen (vgl. Art. 67 und 68 Abs. 5 BGG e contrario).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird, soweit darauf einzutreten ist, gutgeheissen und das Urteil der Einzelrichterin des Verwaltungsgerichts des Kantons Zürich vom 4. Juni 2020 aufgehoben. Der Beschwerdeführer ist unverzüglich aus der Ausschaffungshaft zu entlassen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdeführers eine reduzierte Parteientschädigung von Fr. 2'200.-- zu bezahlen.
4.
Die Sache wird zur Neuregelung der Kosten- und Entschädigungsfolgen der vorangegangenen Verfahren an das Verwaltungsgericht des Kantons Zürich zurückgewiesen.
5.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, Einzelrichterin, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 16. Juli 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: König