Sachverhalt:
A.
A._ stammt aus Äthiopien. Im Jahr 2012 reiste er in die Schweiz ein. Ein von ihm gestelltes Asylgesuch wurde am 3. Oktober 2014 rechtskräftig abgewiesen, worauf A._ vorübergehend untergetaucht ist. Am 7. September 2015 wurde ein zweites Asylgesuch von A._ rechtskräftig abgewiesen. Das Migrationsamt des Kantons Solothurn (nachfolgend: Migrationsamt) lehnte es in der Folge ab, A._ eine Aufenthaltsbewilligung wegen eines schwerwiegenden persönlichen Härtefalls zu erteilen. Am 6. Februar 2020 ordnete das Migrationsamt die Ausschaffungshaft für drei Monate an.
A._ weigerte sich am 28. Februar 2020, einen Flug in seine Heimat anzutreten. Eine begleitete Ausschaffung konnte am 20. März 2020 wegen der Corona-Pandemie nicht durchgeführt werden.
Die Ausschaffungshaft wurde zwei Mal und zuletzt mit Entscheid des Haftgerichts des Kantons Solothurn vom 4. August 2020 bis zum 4. November 2020 verlängert.
B.
A._ focht den erwähnten Entscheid des Haftgerichts mit Beschwerde beim Verwaltungsgericht des Kantons Solothurn an. Dieses wies die Beschwerde am 3. September 2020 ab (Dispositiv-Ziff. 1 des Urteils).
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 17. September 2020 beantragt A._ beim Bundesgericht, unter Aufhebung von Dispositiv-Ziff. 1 des Urteils des Verwaltungsgerichts des Kantons Solothurn sei er unverzüglich aus der Haft zu entlassen und eventualiter sei die Sache zur weiteren Abklärung sowie zur Neubeurteilung an dieses Gericht zurückzuweisen. Ferner ersucht er um unentgeltliche Rechtspflege und unentgeltliche Verbeiständung.
Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts lehnte es am 22. September 2020 ab, den Beschwerdeführer superprovisorisch aus der Ausschaffungshaft zu entlassen.
Das Migrationsamt, das Haftgericht und das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Staatssekretariat für Migration (SEM) liess sich mit Schreiben vom 28. September 2020 (eingegangen beim Bundesgericht am 29. September 2020) zur Vollziehbarkeit der Wegweisung des Beschwerdeführers nach Äthiopien vernehmen.
Mit einer weiteren auf den 28. September 2020 datierenden, am 1. Oktober 2002 eingegangenen Eingabe stellte das Staatssekretariat für Migration dem Bundesgericht die Kopie eines für den Beschwerdeführer ausgestellten Laissez-passers zu.
Der Beschwerdeführer hält mit Schreiben vom 30. September 2020 an seiner Beschwerde fest.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Entscheid über eine Zwangsmassnahme im Ausländerrecht kann die betroffene Person mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht gelangen (Art. 82 i.V.m. <ref-law>; vgl. Urteile 2C_386/2020 vom 9. Juni 2020 E. 1.1; 2C_65/2020 vom 18. Februar 2020 E. 1; 2C_312/2018 vom 11. Mai 2018 E. 1). Wegen des mit der Anordnung ausländerrechtlicher Administrativhaft verbundenen schweren Eingriffs in die persönliche Freiheit kommt dem entsprechenden Freiheitsentzug eigenständige Bedeutung zu; die Haft erscheint nicht als bloss untergeordnete Vollzugsmassnahme zur Wegweisung, weshalb der Ausschlussgrund von <ref-law> der Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht entgegensteht (<ref-ruling> E. 1.1.3 S. 139 f.; <ref-ruling> E. 5.5 S. 101 f.; Urteil 2C_442/2020 vom 24. Juni 2020 E. 1.1). Auf die frist- und formgerecht eingereichte Beschwerde (Art. 42 und Art. 100 Abs. 1 BGG) des hierzu legitimierten Beschwerdeführers (<ref-law>) ist daher 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 Begründungspflicht (<ref-law>), 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>; <ref-ruling> E. 3 S. 415; <ref-ruling> E. 2.2 S. 232).
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie ihn die Vorinstanz festgestellt hat (<ref-law>), es sei denn, dieser erweise sich in einem entscheidwesentlichen Punkt als offensichtlich falsch (d.h. willkürlich) oder unvollständig (<ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.; <ref-ruling> E. 1.3 S. 351). Zur Sachverhaltsfeststellung gehört auch die auf Indizien gestützte Beweiswürdigung (<ref-ruling> E. 2.3 S. 265 ff.). Rügt die beschwerdeführende Partei eine offensichtlich unrichtige Sachverhaltsfeststellung, haben ihre Vorbringen den Anforderungen von <ref-law> zu genügen (<ref-ruling> E. 90.2.3.6 S. 96; <ref-ruling> E. 1.4.3 S. 255).
Das Bundesgericht stellt aufgrund der grundsätzlichen Bindung an den im angefochtenen Entscheid festgestellten Sachverhalt (<ref-law>) in Fällen wie dem vorliegenden praxisgemäss auf die sachverhaltlichen Elemente im Zeitpunkt des angefochtenen Entscheids ab (vgl. Urteile 2C_386/2020 vom 9. Juni 2020 E. 4.2.2; 2C_442/2020 vom 24. Juni 2020 E. 5.3.1). Es kann echte Noven grundsätzlich nicht berücksichtigen (<ref-law>; <ref-ruling> E. 2.1 S. 343 f.). Dies gilt indessen nicht, wenn sich die Umstände seit dem angefochtenen Entscheid zugunsten des Betroffenen derart verändert haben, dass der Haftrichter auf ein Haftentlassungsgesuch auch ausserhalb der Sperrfristen hätte eintreten und dieses gestützt auf die neuen Umstände gegebenenfalls hätte gutheissen müssen (vgl. Art. 80 Abs. 5 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer und über die Integration [Ausländer- und Integrationsgesetz, AIG; SR 142.20]; <ref-ruling> E. 4.2.1 S. 62; <ref-ruling> E. 3b/bb und 3c S. 222 ff.; <ref-ruling> E. 3a S. 5 f.). In diesem Rahmen können etwa die vom Bundesgericht eingeholten Amtsberichte des Staatssekretariats für Migration und die darin enthaltenen Angaben berücksichtigt werden, um die Rechtmässigkeit der Aufrechterhaltung der ausländerrechtlichen Festhaltung zu beurteilen (vgl. Urteile 2C_408/2020 vom 21. Juli 2020 E. 3.3; 2C_1017/2012 vom 30. Oktober 2012 E. 2; 2C_518/2020 vom 10. Juli 2020 E. 4.3.2).
Vorliegend reichte das Staatssekretariat für Migration mit Eingabe vom 28. September 2020 ein Laissez-passer für den Beschwerdeführer ein. Da dieses Laissez-passer im Zeitpunkt des Erlasses des angefochtenen Urteils unbestrittenermassen noch nicht vorlag und dieses Laissez-passer keine Gutheissung eines Haftentlassungsgesuches zur Folge haben müsste, handelt es sich um ein unzulässiges und damit nicht zu berücksichtigendes echtes Novum. Im Folgenden ist daher entsprechend den vorinstanzlichen Feststellungen davon auszugehen, dass bei Erlass des angefochtenen Urteils (noch) kein Laissez-passer für den Beschwerdeführer vorlag. Auch ist einzig die Sachlage in diesem Zeitpunkt zu beurteilen (vgl. dazu auch hinten E. 3.5).
3.
Der Beschwerdeführer rügt in sachverhaltlicher Hinsicht sinngemäss, die Vorinstanz habe willkürlich festgestellt, es sei vor Oktober 2020 möglich, bei der äthiopischen Botschaft ein neues Laissez-passer für ihn erhältlich zu machen. Im Zeitpunkt des angefochtenen Urteils habe nicht davon ausgegangen werden können, dass die konkret in Frage stehende Ausschaffung durchführbar sei.
3.1. Im angefochtenen Urteil wurde ausgeführt, das Staatssekretariat für Migration bemühe sich schon seit Längerem um die Ausreise. Es habe "nun" Verzögerungen gegeben "wegen der Weigerung der äthiopischen Botschaft, neue Reisepapiere auszustellen, offenbar auf Druck Dritter hin". Das Staatssekretariat für Migration wolle sich bereits anfangs September 2020 in Genf um die Papierbeschaffung kümmern. Es sollte - so die Vorinstanz im angefochtenen Urteil - vor Oktober 2020 möglich sein, ein neues Laissez-passer zu erhalten (E. II./3 des angefochtenen Urteils).
3.2. Anscheinend stützte sich die Vorinstanz für ihre Annahme, dass vor Oktober 2020 ein neues Laissez-passer für den Beschwerdeführer vorliegen werde, auf eine entsprechende Einschätzung des Staatssekretariats für Migration und dessen Bekundung der Absicht, sich anfangs September 2020 in Genf um die Beschaffung der notwendigen Papiere zu kümmern. Wie der Beschwerdeführer zutreffend rügt, legt die Vorinstanz aber nicht dar, wie sie bzw. das Staatssekretariat für Migration zum Schluss kam, dass noch vor Oktober 2020 ein Laissez-passer beschafft werden kann. Insbesondere wurden im angefochtenen Urteil keine Umstände festgestellt, welche darauf schliessen lassen, dass das Staatssekretariat für Migration die äthiopische Botschaft innert vernünftiger Frist zu einem Umdenken, also zur Aufgabe der bisherigen Verweigerungshaltung bezüglich der Ausstellung eines neuen Laissez-passers für den Beschwerdeführer würde bewegen können. Ebenso wenig wurde festgehalten, dass im Zeitpunkt des Erlasses des angefochtenen Urteils der behaupteterweise auf die Botschaft ausgeübte Druck Dritter nachgelassen hat oder von der Botschaft nicht mehr als relevant erachtet wird. Seitens der Vorinstanz ebenfalls nicht festgestellt worden ist, dass dieser angebliche Druck Dritter - so er denn überhaupt als erstellt erachtet werden kann - indirekt dem Beschwerdeführer zuzuschreiben wäre.
3.3. Mit Blick darauf, dass es - wie gesehen - an entscheidwesentlichen Feststellungen im angefochtenen Urteil fehlt, ist der darin festgestellte Sachverhalt zu ergänzen (vgl. <ref-law>).
3.3.1. Aus den Akten geht hervor, dass die äthiopische Botschaft immer wieder - namentlich im Rahmen eines 50-minütigen Telefongesprächs vom 15. Mai 2020 - angehalten wurde, ihrer Pflicht zur Ausstellung des Ersatzreisedokumentes nachzukommen (vgl. Akten Migrationsamt, pag.-Nr. 429 und 376). Noch am 9. Juni 2006 erklärte das Staatssekretariat für Migration gemäss einer Aktennotiz sinngemäss, dass sich die Botschaft von ihm nicht unter Druck setzen lasse und der Botschafter noch nicht zugesagt habe, ein Laissez-passer auszustellen (Akten Migrationsamt, pag.-Nr 377). Nach Angaben des Staatssekretariats vom 13. Juli 2020 gab die Botschaft auf telefonische Nachfrage hin zu verstehen, dass der Fall noch angeschaut werden müsse und sich nach Ansicht der Botschaft infolge eines Ausnahmezustandes in Äthiopien jedenfalls vor dem 8. September 2020 keine Ausschaffung empfehle (Akten Migrationsamt, pag.-Nr. 396). Zwar hat das Staatssekretariat am 27. Juli 2020 gegenüber dem Migrationsamt erklärt, es sei sicher, dass in nächster Zeit Bewegung in die Sache komme und in den nächsten zwei Monaten ein Laissez-passer ausgestellt werde (Akten Migrationsamt, pag.-Nr. 397). Dabei räumte das Staatssekretariat für Migration allerdings ein, dass noch kein offizielles "Feedback" seitens der Botschaft bestehe; ihre optimistische Einschätzung hinsichtlich des Ausstellungszeitpunktes des Laissez-passers stützte es damals anscheinend im Wesentlichen einzig auf ihre Annahme, dass der Fall bei einer weiteren Verschleppung auf höchster Ebene der äthiopischen Behörden diskutiert würde.
Bereits am 30. Juli 2020 erklärte das Staatssekretariat für Migration sodann in Abweichung von seiner Einschätzung vom 27. Juli 2020, es könne nicht genau gesagt werden, ob und wann ein Laissez-passer ausgestellt werde. Es führte aus, die Botschaft suche im Fall des Beschwerdeführers nach Ausreden und behaupte, es müssten zusätzliche Abklärungen getroffen werden (Akten Migrationsamt, pag.-Nr. 399). Am 11. August 2020 teilte das Staatssekretariat dem Migrationsamt mit, es habe nach einem personellen Wechsel in der Botschaft mit der zuständigen Person telefonieren können, es werde anfangs September 2020 ein Gespräch in der Botschaft in Genf führen und der derzeitige Ausnahmezustand in Äthiopien gehe anfangs September 2020 zu Ende (Akten Migrationsamt, pag.-Nr. 399).
3.3.2. Das Migrationsamt forderte das Staatssekretariat während der Hängigkeit des Verfahrens vor der Vorinstanz auf, vor dem Hintergrund, "dass die Papierbeschaffung aus Aussensicht [...] tatsächlich als blockiert angesehen werden könnte", schriftliche Informationen namentlich zum Stand der Papierbeschaffung zu liefern (Akten Migrationsamt, pag. 508). Daraufhin verfasste das Staatssekretariat am 24. August 2020 eine aktenkundige Stellungnahme, welche offensichtlich von der Vorinstanz im vorliegend interessierenden Zusammenhang herangezogen worden ist. Darin führte das Staatssekretariat insbesondere Folgendes aus (Akten Migrationsamt, pag.-Nr. 511) :
"Am 16. April 2020 wurde bei der äthiopischen Botschaft eine Erneuerung des Laissez-Passer für N xxx xxx [= Kürzel für den Beschwerdeführer] beantragt. Gemäss der Vereinbarung zwischen Äthiopien und der Schweiz [= vgl. "Exchange of notes regarding the Admission Procedures for the Return of Ethiopians without legal status to reside in Switzerland" vom 4. Januar 2019] müsste eine Erneuerung eines Laissez-Passers innerhalb von drei Arbeitstagen erfolgen. Die Praxis hat gezeigt, dass normalerweise 2-3 Wochen vergehen, bis die äthiopische Botschaft ein Laissez-Passer versendet.
Da für N xxx xxx jedoch innerhalb dieser Frist kein Ersatzreisedokument eingetroffen ist, wurde das Gespräch mit der äthiopischen Botschaft gesucht. Dem SEM wurde mitgeteilt, dass gewisse Personen aus der äthiopischen Diaspora die äthiopische Botschaft und den äthiopischen Botschafter massiv unter Druck gesetzt haben, damit kein Laissez-Passer für N xxx xxx ausgestellt wird. Ebenfalls wurde betont, dass sich die Botschaft - trotz dieser Einschüchterungsversuche - an die Vereinbarung halten werde und ein Laissez-Passer zu einem späteren Zeitpunkt ausstellen werde. Als Grund für die zeitliche Verzögerung wurde u.a. die angespannte Lage in Äthiopien aufgeführt.
Während den folgenden Wochen wurde mehrmals die hängige Ausstellung des Ersatzreisedokuments für N xxx xxx mit der äthiopischen Botschaft thematisiert. Gemäss Aussage der äthiopischen Botschaft kam es aufgrund der politischen Lage in der Heimat im Juli 2020 zu Demonstrationen vor der äthiopischen Botschaft in Genf, was als Grund angegeben wurde, wieso zum jetzigen Zeitpunkt die Ausstellung des betreffenden Laissez-Passers verschoben werden müsse. Dessen ungeachtet wurde jedoch bestätigt, dass sich die Botschaft an die Vereinbarung halten und das Laissez-Passer zu einem späteren Zeitpunkt ausstellen werde.
Nächste Schritte:
Bereits mit der Botschaft abgesprochen ist, dass das SEM anfangs September 2020 nach Genf reisen wird, um die neue, zuständige Ansprechsperson für diesen Fall kennenzulernen. Bei dieser Gelegenheit soll einmal mehr der äthiopischen Botschaft die Dringlichkeit der Ausstellung des Laissez-Passers vermittelt werden.
Das SEM geht davon aus, dass aufgrund der überlangen Verzögerung der Ausstellung eines Laissez-Passers - dies klar entgegen den Vorgaben der Vereinbarung - ein weiteres Hinhalten für die äthiopische Botschaft kaum möglich sein wird. Eine Ausstellung des Laissez-Passers vor Oktober 2020 sollte deshalb realisierbar sein."
3.4. Mit Blick auf die erwähnten Ausführungen des Staatssekretariats für Migration (vgl. E. 3.3) muss als in tatsächlicher Hinsicht als erstellt gelten, dass die äthiopische Botschaft sich mindestens von Mitte Mai 2020 bis zum Zeitpunkt des Erlasses des angefochtenen Entscheids vom 3. September 2020 mit unterschiedlichen Begründungen wiederholt weigerte, das erforderliche Ersatzreisepapier bzw. ein neues Laissez-passer für den Beschwerdeführer auszustellen. Zwar beteuerte die Botschaft nach Angaben des Staatssekretariats mehrfach, den völkerrechtlichen Verpflichtungen nachkommen und zu einem späteren Zeitpunkt ein Laissez-passer ausstellen zu wollen. Diesen Beteuerungen konnte indessen im Zeitpunkt des angefochtenen Urteils kein entscheidendes Gewicht beigemessen werden, und zwar selbst unter Berücksichtigung der grundsätzlich im zwischenstaatlichen Verkehr greifenden Vermutung, dass ein Staat entsprechend seinen abkommensrechtlichen Verpflichtungen seinen Staatsangehörigen nicht das Recht verwehrt, in sein Hoheitsgebiet zurückzukehren (vgl. zu diesen Verpflichtungen und zur genannten Vermutung hinten E. 5.4.3) :
Zum einen hat die Botschaft wechselnde Begründungen für die eingetretenen Verzögerungen geliefert, und waren diese Begründungen teilweise fraglich. Insbesondere ist nämlich angesichts des Umstandes, dass ein Laissez-passer über eine längere Zeitspanne gültig sein kann, nicht nachvollziehbar, inwiefern nicht vor Beendigung des Ausnahmezustandes in Äthiopien ein Laisser-passer hätte ausgestellt und die Festlegung des konkreten Zeitpunkts der Rückführung den schweizerischen Behörden hätte überlassen werden können. Nicht von ungefähr hat denn auch das Staatssekretariat für Migration noch am 30. Juli 2020 angenommen, die Botschaft suche nach Ausreden für die Nichtausstellung des Laissez-passers.
Zum anderen hatte zwar bei Erlass des angefochtenen Urteils die Botschaft die Bereitschaft ihrer neuen, zuständigen Ansprechsperson für ein Gespräch mit dem Staatssekretariat für Migration anfangs September 2020 signalisiert, doch fehlte es nach wie vor an einer konkreten Zusage der Botschaft, die Ausstellung des Laissez-passers voranzutreiben.
Vor diesem Hintergrund hätte der Vorinstanz bei Erlass des angefochtenen Urteils die Prognose des Staatssekretariats für Migration, wonach vor Oktober 2020 ein Laissez-passer vorliegen werde, als unhaltbar erscheinen müssen. Denn nachdem sich die Botschaft seit Monaten über die Äthiopien treffenden völkerrechtlichen Verpflichtungen zur Bereitstellung der notwendigen Reisepapiere (vgl. dazu auch hinten E. 5.4.3) hinweggesetzt hatte, bestand kein begründeter Anlass zur Annahme, dass allein durch den Zeitablauf der Druck auf die Botschaft, sich an diese Verpflichtungen zu halten, in absehbarer Zeit hinreichend gross sein wird, um sie zu einem Einlenken zu bewegen. Zur Annahme, dass die äthiopische Botschaft in einem dem konkreten Fall angemessenen Zeitraum das erforderliche Ersatzreisepapier liefern wird, berechtigte auch nicht etwa der Umstand, dass sich ein Ende des von der Botschaft geltend gemachten Ausnahmezustandes in Äthiopien abzeichnete, musste doch aufgrund des Verhaltens der Botschaft damit gerechnet werden, dass es einen neuen Grund für ein weiteres Nichtausstellen des Laissez-passers anrufen wird.
Im Zeitpunkt des Erlasses des angefochtenen Urteils hätte die Vorinstanz nach dem Gesagten davon ausgehen müssen, dass sich die äthiopische Botschaft aus nicht dem Beschwerdeführer zuzurechnenden Gründen seit Längerem konsequent weigerte und nach wie vor weigert, das erforderliche Laissez-passer auszustellen. Die Feststellung der Vorinstanz, wonach im Zeitpunkt des Erlasses des angefochtenen Urteils anzunehmen war, dass vor Oktober 2020 ein neues Laissez-passer für den Beschwerdeführer vorliegen werde, erscheint als offensichtlich unrichtig bzw. als willkürlich.
3.5. Zwar ist in den im bundesgerichtlichen Verfahren eingereichten Rechtsschriften des Beschwerdeführers, des Migrationsamts und des Staatssekretariats für Migration davon die Rede, dass Vertreter des Staatssekretariats für Migration am 9. September 2020 gemäss einem E-Mail vom 10. September 2020 zwecks Besuchs der neuen äthiopischen Deputy Head of Mission und mit dem Ziel der Lösungsfindung betreffend die Ausstellung eines Ersatzreisedokuments für den Beschwerdeführer auf der äthiopischen Botschaft waren und für die erste Oktoberwoche - nach Rückkehr des abwesenden Botschafters in die Schweiz - eine erneute Kontaktaufnahme mit dieser Botschaft geplant war. Die diesbezüglichen Ausführungen und Beweismittel sind jedoch im vorliegenden Verfahren als echte Noven unbeachtlich, da sie einen Zeitraum nach dem Erlass des angefochtenen Urteils betreffen (bzw. nach dem Erlass des angefochtenen Urteils entstanden sind) und es nicht um Tatsachen geht, aufgrund welcher der Haftrichter auf ein Haftentlassungsgesuch auch ausserhalb der Sperrfristen hätte eintreten und dieses gegebenenfalls gestützt auf die neuen Umstände hätte gutheissen müssen (vgl. E. 2.2 hiervor).
4.
4.1. Zu prüfen ist sodann die Zulässigkeit der Haft.
Wurde eine Wegweisung ausgesprochen, kann die zuständige Behörde den betroffenen Ausländer zur Sicherstellung von deren Vollzug unter anderem in Ausschaffungshaft nehmen bzw. in dieser belassen, wenn konkrete Anzeichen befürchten lassen, dass er sich der Ausschaffung entziehen will, oder sein bisheriges Verhalten darauf schliessen lässt, dass er sich behördlichen Anordnungen widersetzt (Art. 76 Abs. 1 lit. b Ziff. 3 und 4 AIG). Der Haftgrund muss prioritär dem zulässigen Haftzweck, nämlich der Sicherstellung des Vollzugs der Wegweisung dienen ("Zweckgebundenheit"; vgl. Urteil 2C_510/2020 vom 7. Juli 2020 E. 2.1).
4.2. Der Beschwerdeführer ist gemäss den Feststellungen im angefochtenen Urteil nach der rechtskräftigen Abweisung seines ersten Asylgesuchs untergetaucht. Überdies hat er sich am 28. Februar 2020, nach rechtskräftiger Wegweisung, geweigert, einen Rückflug nach Äthiopien anzutreten. Gestützt auf dieses Verhalten durften die kantonalen Behörden davon ausgehen, dass er sich künftig für den Vollzug der Wegweisung nicht zu ihrer Verfügung halten dürfte.
5.
Die Haft muss sodann verhältnismässig sein. Der Beschwerdeführer rügt, dass seine Inhaftierung unverhältnismässig sei und gegen Art. 5 Ziff. 1 EMRK verstosse.
5.1. Die Ausschaffungshaft soll den Vollzug der Entfernungsmassnahme sicherstellen und muss ernsthaft geeignet sein, diesen Zweck zu erreichen, was nicht (mehr) der Fall ist, wenn die Wegweisung trotz der behördlichen Bemühungen nicht in absehbarer Zeit vollzogen werden kann (<ref-ruling> E. 4.1.1 S. 60 mit Hinweisen). Die Haft hat, weil unverhältnismässig, dann als unzulässig zu gelten, wenn triftige Gründe für die Undurchführbarkeit des Vollzugs sprechen oder praktisch feststeht, dass er sich innert vernünftiger Frist kaum wird realisieren lassen (vgl. <ref-ruling> E. 2c S. 172; <ref-ruling> E. 2; <ref-ruling> E. 3 S. 152 f.). Dies ist in der Regel bloss der Fall, wenn die Ausschaffung auch bei gesicherter Kenntnis der Identität oder der Nationalität des Betroffenen bzw. trotz seines Mitwirkens bei der Papierbeschaffung mit grosser Wahrscheinlichkeit als ausgeschlossen erscheint. Nur falls keine oder bloss eine höchst unwahrscheinliche, rein theoretische Möglichkeit besteht, die Wegweisung zu vollziehen, ist die Haft aufzuheben, nicht indessen bei einer ernsthaften, wenn auch allenfalls (noch) geringen Aussicht hierauf (<ref-ruling> E. 4.1.3 S. 61). Zu denken ist etwa an eine ausdrückliche oder zumindest klar erkennbare und konsequent gehandhabte Weigerung eines Staates, gewisse Staatsangehörige zurückzunehmen (<ref-ruling> E. 4.1.3 S. 61; Urteil 2C_252/2008 vom 10. Juni 2008 E. 2.2; vgl. ferner Urteil 2C_915/2017 vom 24. November 2017 E. 4.3).
5.2. Unter Vorbehalt einer Beeinträchtigung der öffentlichen Ordnung durch die betroffene Person ist die Frage nach der Durchführbarkeit des Wegweisungsvollzugs nicht notwendigerweise im Hinblick auf die maximal mögliche Haftdauer, sondern vielmehr auf einen den gesamten Umständen des konkreten Falls angemessenen Zeitraum hin zu beurteilen (<ref-law>, vgl. <ref-ruling> E. 4.1.3 S. 61; <ref-ruling> E. 3b/bb S. 223; Urteil 2C_442/2020 vom 24. Juni 2020 E. 5.1).
5.3. Die Vorinstanz ging davon aus, dass der Vollzug der Wegweisung des Beschwerdeführers in absehbarer Zeit möglich sei. Sie erwog, die Corona-Pandemie sei kein Hinderungsgrund für Flüge nach B._ mehr. Ein Blick ins Internet zeige, dass verschiedene Unternehmen Flüge dorthin anbieten würden. Weiter verwies sie - wie bereits erwähnt - darauf, dass es (nach ihrer Einschätzung) vor Oktober 2020 möglich sein werde, ein neues Laissez-passer zu erhalten.
5.4.
5.4.1. Für die Frage, ob der Vollzug der Wegweisung absehbar war, ist auf den Zeitpunkt des angefochtenen Entscheids abzustellen (vgl. vorne E. 2.2 und E. 3.5; Urteil 2C_518/2020 vom 10. Juli 2020 E. 4.3.1 und E. 4.3.2).
5.4.2. Mit Blick auf das hiervor Ausgeführte ist davon auszugehen, dass im Zeitpunkt des Urteils vom 3. September 2020 aufgrund des Verhaltens der äthiopischen Botschaft entgegen der Vorinstanz noch nicht absehbar war, ob und wann der Beschwerdeführer die erforderlichen Reisepapiere erhalten wird (vgl. E. 3.4). Zwar erklärte das Staatssekretariat für Migration, sich anfangs September 2020 in Genf um die Beschaffung der notwendigen Dokumente zu kümmern, doch bestanden im Zeitpunkt des Erlasses des angefochtenen Urteils aufgrund der Vorgeschichte konkrete Hinweise, dass die äthiopische Botschaft über einen absehbaren Zeitraum hinaus an ihrer manifesten Weigerung, ein neues Laissez-passer auszustellen, festhalten wird. Allein die angekündigte Intervention des Staatssekretariats für Migration in Genf kann unter diesen Umständen nicht genügen, um mehr als eine höchst unwahrscheinliche, rein theoretische Möglichkeit des Vollzugs der Wegweisung anzunehmen, zumal angesichts der mehrmonatigen, hiervor skizzierten Vorgeschichte seit Einreichung des Gesuchs um Ausstellung eines neuen Laissez-passers keine Anhaltspunkte dafür bestanden, dass diese Bemühungen in Bezug auf die Beschaffung der erforderlichen Reisepapiere bei der Botschaft neu zielführend sein werden (vgl. E. 3.4 hiervor).
5.4.3. Wohl ist grundsätzlich völkerrechtlich nach Treu und Glauben zu vermuten, dass dem Betroffenen seitens des Heimatstaates die Einreise in dessen Hoheitsgebiet in Übereinstimmung mit den diesen Staat treffenden völkerrechtlichen Verpflichtungen nicht verwehrt wird (vgl. <ref-ruling> E. 4.1.2), und ist deshalb nicht leichthin darauf zu schliessen, dass dieser Staat die Rücknahme seines Staatsangehörigen in klar erkennbarer und konsequenter Weise verweigert (vgl. E. 5.1 hiervor). Auch muss dies a fortiori dann gelten, wenn der Betroffene (wie vorliegend) bereits einmal durch mangelnde Kooperation eine Rückführung verunmöglichte, zumal die Vorbereitung des Vollzugs bei fehlender Kooperation der betroffenen Person eine gewisse Zeit in Anspruch nimmt (vgl. <ref-ruling> E. 4.1.2 S. 60; Urteile 2C_490/2019 vom 18. Juni 2019 E. 6.1.1; 2C_312/2018 vom 11. Mai 2018 E. 4.2.5; 2C_846/2017 vom 30. Oktober 2017 E. 4.3.2). Beim hier einzig zu beurteilenden konkreten Einzelfall fällt aber entscheidend ins Gewicht, dass im Zeitpunkt des Erlasses des angefochtenen Urteils seit Längerem unternommene Bemühungen des Staatssekretariats für Migration um Vorbereitung der Ausreise durch die Verweigerung der äthiopischen Botschaft, (erneut) ein Laissez-passer auszustellen, vereitelt worden sind. Anders als etwa bei der mit dem Urteil 2C_252/2008 vom 10. Juni 2008 (in E. 2.4) beurteilten Konstellation verhielt es sich dabei nach den Feststellungen im angefochtenen Urteil auch nicht etwa so, dass sich andere Behörden des Heimatstaates positiv zur Rücknahme von ausgeschafften Landsleuten geäussert und eine solche in Aussicht gestellt hätten.
Die vage Möglichkeit, dass das Vollzugshindernis potentiell aufgrund Einlenkens der äthiopischen Botschaft in absehbarer Zeit entfallen könnte, reicht nicht aus, um die Ausschaffungshaft aufrechtzuerhalten (vgl. BGE <ref-ruling> E. 3b/bb S. 223 f.; Urteile 2C_442/2020 vom 24. Juni 2020 E. 5.3.3; 2C_386/2020 vom 9. Juni 2020 E. 4.2.4; 2C_312/2020 vom 25. Mai 2020 E. 2.3.2).
5.5. Nach dem Gesagten bestand im Zeitpunkt des angefochtenen Urteils nur eine höchst unwahrscheinliche, rein theoretische Möglichkeit, dass der Vollzug der Wegweisung des Beschwerdeführers innert absehbarer Frist wird durchgeführt werden können. Richtigerweise hätte die Vorinstanz daher dem Haftentlassungsgesuch gestützt auf <ref-law> stattgeben und 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.
6.
6.1. Die Beschwerde ist somit gutzuheissen, das Urteil des Verwaltungsgerichts Solothurn vom 20. Mai 2020 aufzuheben und der Beschwerdeführer umgehend aus der Ausschaffungshaft zu entlassen. Ob gegebenenfalls andere, für den Fall des Vorliegens einer rechtskräftigen Wegweisungsverfügung vorgesehene Massnahmen (wie etwa - sofern die Möglichkeit einer freiwilligen Ausreise nicht an einem objektiven, in seiner Dauer zeitlich [noch] nicht absehbaren technischen Hindernis scheitert, sondern allein an dem Verhalten der ausländischen Person [vgl. zur Publikation bestimmtes Urteil 2C_408/2020 vom 21. Juli 2020 E. 4.2] - Eingrenzung [<ref-law>] oder Durchsetzungshaft [<ref-law>]) in Frage kommen, ist nicht am Bundesgericht zu entscheiden.
Auf die Rügen betreffend Verletzung des rechtlichen Gehörs ist ausgangsgemäss nicht weiter einzugehen.
6.2. Es sind keine Kosten für das bundesgerichtliche Verfahren geschuldet (<ref-law>). Der Kanton Solothurn hat die Rechtsvertreterin des Beschwerdeführers angemessen zu entschädigen (vgl. <ref-law>).
Die Rechtsvertreterin hat Honorarnoten über Fr. 2'785.60 eingereicht; diese sind insgesamt überhöht: Rechtsanwältin Lea Hungerbühler hat beim Bundesgericht mehrere, inhaltlich praktisch identische Beschwerden bezüglich der Auswirkung der Corona-Pandemie auf die Administrativhaft eingereicht; ihr Aufwand war im Hinblick auf die jeweils analogen Ausführungen vorliegend - soweit es ausschliesslich um diese Pandemie und deren Folgen für die Ausschaffung ging - beschränkt (vgl. Urteile 2C_518/2020 vom 10. Juli 2020 E. 6.2; 2C_510/2020 vom 7. Juli 2020 E. 7.2.2). Es rechtfertigt sich, die Parteientschädigung auf Fr. 2'500.-- festzusetzen.
Durch die Zusprechung einer Parteientschädigung an die Rechtsvertreterin des Beschwerdeführers wird das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege und unentgeltliche Verbeiständung gegenstandslos.
Die Vorinstanz wird über die Kosten- und Entschädigungsfolgen des kantonalen Verfahrens neu zu befinden haben (Art. 67, Art. 68 Abs. 5 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 3. September 2020 wird aufgehoben.
2.
Der Beschwerdeführer ist unverzüglich aus der Ausschaffungshaft zu entlassen.
3.
Es werden keine Gerichtskosten erhoben.
4.
Der Kanton Solothurn hat der Rechtsvertreterin des Beschwerdeführers eine Parteientschädigung von Fr. 2'500.-- zu bezahlen.
5.
Zur Neuregelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens wird die Sache an das Verwaltungsgericht des Kantons Solothurn zurückgewiesen.
6.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 21. Oktober 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: König