gemäss Art. 13b Abs. 2 ANAG, hat sich ergeben:
A.- Der aus der Demokratischen Republik Kongo stammende M._ kam am 11. Juni 2000 von Paris her ohne Einreiseerlaubnis im Flughafen Zürich-Kloten an. Am 15. Juni 2000 stellte er ein Asylgesuch. Das Bundesamt für Flüchtlinge lehnte dieses am 23. Juni 2000 ab, wies ihn aus der Schweiz weg und ordnete die sofortige Vollstreckbarkeit der Wegweisung an; einer allfälligen Beschwerde wurde die aufschiebende Wirkung entzogen. Die Schweizerische Asylrekurskommission lehnte mit Zwischenentscheid vom 26. Juni 2000 die Wiederherstellung der aufschiebenden Wirkung der am 25. Juni 2000 eingereichten Beschwerde ab. Am 27. Juni 2000 wurde M._ zur Sicherung des Ausschaffungsvollzugs im Flughafenareal angehalten. Der Haftrichter am Bezirksgericht Zürich (im Folgenden: Haftrichter) bestätigte am 29. Juni 2000 die bis zum 27. September 2000 angeordnete Ausschaffungshaft.
Mit Urteil vom 19. Juli 2000 trat die Asylrekurskommission auf die im Asylverfahren erhobene Beschwerde vom 25. Juni 2000 mangels Leistung des geforderten Kostenvorschusses nicht ein.
B.- Am 20. September 2000 beantragte die Fremdenpolizei des Kantons Zürich eine Verlängerung der Ausschaffungshaft um drei Monate. Mit Verfügung vom 21. September 2000 verlängerte der Haftrichter die Haft um zwei Monate bis zum 27. November 2000.
C.- M._ hat mit Postaufgabe vom 21. Oktober 2000 Verwaltungsgerichtsbeschwerde erhoben mit dem Antrag, den Entscheid des Haftrichters vom 21. September 2000 aufzuheben und ihn "unverzüglich aus der Ausschaffungshaft zu entlassen".
D.- Der Haftrichter am Bezirksgericht Zürich hat auf eine Vernehmlassung verzichtet. Die Fremdenpolizei des Kantons Zürich schliesst auf Abweisung der Beschwerde. Das Bundesamt für Ausländerfragen sowie das Bundesamt für Flüchtlinge, denen das Bundesgericht Gelegenheit zur Stellungnahme gegeben hat, haben sich nicht vernehmen lassen. Auch M._ hat sich innert Frist nicht mehr geäussert.

Das Bundesgericht zieht in Erwägung:
1.- Nach Art. 105 Abs. 2 OG ist das Bundesgericht an die Feststellung des Sachverhaltes gebunden, wenn eine richterliche Behörde als Vorinstanz den Sachverhalt nicht offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen erhoben hat. Ausgeschlossen ist damit auch die Berücksichtigung neuer tatsächlicher Vorbringen bzw. nachträglicher Veränderungen des Sachverhalts.
Das Bundesgericht prüft den Haftentscheid deshalb grundsätzlich lediglich aufgrund der Sachlage, wie sie sich dem Haftrichter präsentierte (<ref-ruling> E. 3a S. 221, mit Hinweisen).
2.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen, soweit die Voraussetzungen von Art. 13b des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG, SR 142. 20) erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt (vgl. <ref-ruling> E. 2 S. 61; <ref-ruling> E. 3a S. 374; <ref-ruling> ff.), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist (BGE <ref-ruling> E. 3a S. 374, 377 E. 2a S. 379). Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (BGE <ref-ruling> E. 3a S. 374; <ref-ruling> E. 1 S. 3). Weiter müssen die Haft verhältnismässig (<ref-ruling> E. 4 S. 383; <ref-ruling> E. 2c S. 198; vgl. auch BGE <ref-ruling> E. 3 S. 153) und die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. <ref-ruling> E. 5 S. 384; <ref-ruling> E. 3 S. 152 ff.). Auf Seiten der Behörden ist die Papierbeschaffung mit dem nötigen Nachdruck zu verfolgen (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.). Schliesslich sind die gesetzlichen Anforderungen an die Haftbedingungen zu beachten (vgl. Art. 13c Abs. 3 sowie Art. 13d ANAG; <ref-ruling> E. II 1-5 S. 229 ff.; <ref-ruling> E. 3-8 S. 302 ff.; <ref-ruling> E. 2-8 S. 225 ff.), welche der Beschwerdeführer hier nicht beanstandet.
Nach Art. 13b Abs. 2 ANAG darf die Haft höchstens drei Monate dauern; stehen dem Vollzug der Weg- oder Ausweisung besondere Hindernisse entgegen, so kann die Haft mit Zustimmung der kantonalen richterlichen Behörde um höchstens sechs Monate verlängert werden (Art. 13b Abs. 2 ANAG).
3.- Der Beschwerdeführer ist mit dem Entscheid des Bundesamtes für Flüchtlinge vom 23. Juni 2000 aus der Schweiz weggewiesen worden. Die Fremdenpolizei sowie der Haftrichter stützen die Haft auf Art. 13b Abs. 1 lit. c ANAG. Nach dieser Bestimmung kann Ausschaffungshaft verfügt werden, wenn konkrete Anzeichen befürchten lassen, dass sich der Ausländer der Ausschaffung entziehen will (Gefahr des Untertauchens).
Das trifft namentlich zu, wenn der Ausländer bereits einmal untergetaucht ist, behördlichen Anordnungen keine Folge leistet oder sonst wie durch erkennbar unglaubwürdige und widersprüchliche Angaben die Vollzugsbemühungen der Behörden erschwert (BGE <ref-ruling> E. 3b/aa S. 375, mit Hinweisen).
Da die Untertauchensgefahr vom Gesetz generalklauselartig definiert wird, ist insoweit das gesamte Verhalten des Beschwerdeführers von seiner erstmaligen Einreise in die Schweiz an massgeblich. Der illegale Aufenthalt in der Schweiz, die Tatsache, dass der Betroffene keine Papiere besitzt und nur mangelhaft an deren Beschaffung mitwirkt sowie das Fehlen eines festen Aufenthaltsorts oder Mittellosigkeit genügen für sich allein nicht für die Annahme von Untertauchensgefahr, können diese jedoch gegebenenfalls zusammen mit anderen Hinweisen indizieren (vgl. <ref-ruling> E. 2a S. 50 f.).
Für die Gefahr des Untertauchens spricht vorliegend, dass der Beschwerdeführer unter anderem beim Haftrichtertermin vom 21. September 2000 klar zu erkennen gab, dass er zurzeit keinesfalls in sein Herkunftsland zurückkehren will (E. 3b/bb des nicht veröffentlichten Urteils i.S.
Jobouri vom 4. Oktober 1999; Alain Wurzburger, La jurisprudence récente du Tribunal fédéral en matière de police des étrangers, in RDAF 53/1997, S. 333). Nach der bundesgerichtlichen Rechtsprechung werden zwar bei Ausländern mit hängigem Asylgesuch bzw. nicht rechtskräftig abgeschlossenem Asylverfahren Aussagen, wonach sie die Schweiz nicht verlassen wollen, bei der Beurteilung der Untertauchensgefahr nicht berücksichtigt, denn es darf demjenigen, der um Asyl ersucht, nicht zum Nachteil gereichen, wenn er seiner Furcht vor einer Rückkehr in den Heimatstaat, dem er entflohen ist, Ausdruck verleiht (E. 3b/bb des erwähnten Urteils vom 4. Oktober 1999, mit Hinweis). Insoweit mag der Haftentscheid vom 29. Juni 2000, der sich auf derartige Aussagen des Beschwerdeführers stützte, obwohl über die Beschwerde in dem vor der Ausschaffungshaft eingeleiteten Asylverfahren noch nicht entschieden worden war, fragwürdig erscheinen. Jener Haftentscheid ist indes nicht angefochten worden und damit in Rechtskraft erwachsen; das Bundesgericht kann hierauf nicht mehr zurückkommen. Im Zeitpunkt des Entscheides über die Verlängerung der Haft am 21. September 2000 war das Asylverfahren hingegen rechtskräftig abgeschlossen. Der Beschwerdeführer besitzt sodann keine Papiere. Wie auch das Bundesamt für Flüchtlinge in seinem Asylentscheid ausgeführt hat, ist indes nicht glaubhaft, dass er ohne Ausweis mit einem Passagierflugzeug der Air France von Brazzaville nach Paris und von dort mit einer Maschine der Swissair nach Zürich gelangt sein kann. Nachdem der Beschwerdeführer weitgehend mittellos ist und keinen festen Aufenthaltsort in der Schweiz hat, ist damit die Gefahr des Untertauchens vorliegend zu bejahen.
Aus den Akten der Fremdenpolizei ergibt sich, dass der Beschwerdeführer einen Rückschaffungsversuch der Behörden vom 9. Oktober 2000 zum Scheitern gebracht hat. Das würde an sich das Vorliegen des Haftgrundes des Art. 13b Abs. 1 lit. c ANAG bestätigen. Nachdem sich dieser Vorfall nach dem Haftrichtertermin vom 21. September 2000 ereignet hat, darf er hier allerdings nicht berücksichtigt werden (vgl. E. 1).
4.- a) Gemäss Art. 13c Abs. 5 lit. a ANAG darf die Ausschaffungshaft nur angeordnet oder aufrechterhalten werden, wenn der Vollzug der Weg- oder Ausweisung nicht aus rechtlichen oder tatsächlichen Gründen undurchführbar ist. Sodann haben die Behörden die für den Vollzug der Weg- oder Ausweisung notwendigen Vorkehren umgehend zu treffen (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; vgl. <ref-ruling> E. 5 S. 384; <ref-ruling> E. 3 S. 50 ff.). Andernfalls verstösst die Haft gegen Art. 5 Ziff. 1 lit. f EMRK.
b) Nach entsprechenden Identifizierungsmassnahmen und Vorführung des Beschwerdeführers bei der Botschaft seines Heimatlandes teilte das Bundesamt für Flüchtlinge den Behörden am 11. August 2000 mit, Reisedokumente könnten erstellt werden, sobald Datum und Flug bekannt seien. Das Bundesgericht hat eine Verletzung des Beschleunigungsgebots bejaht, wenn während rund zwei Monaten keinerlei Vorkehren mehr im Hinblick auf die Ausschaffung getroffen wurden, ohne dass die Verzögerung in erster Linie auf das Verhalten ausländischer Behörden oder des Betroffenen selber zurückging (<ref-ruling> E. 3a S. 51, mit Hinweisen). Im Übrigen ist nach den Umständen des Einzelfalles zu beurteilen, ob das Beschleunigungsgebot verletzt wurde (<ref-ruling> E. 3a S. 51, mit Hinweis). Der Beschwerdeführer rügt, es sei aus den Akten nicht ersichtlich, dass sich die Behörden mit den Vorbereitungen zu seiner Ausschaffung beschäftigten.
Bis zum 11. August 2000 liefen die Massnahmen zur Identifizierung des Beschwerdeführers, um anschliessend Reisepapiere erlangen zu können. Hingegen ergibt sich nicht hinreichend aus den Akten, was die Behörden seit diesem Datum unternommen haben. Die Aktennotiz der Fremdenpolizei vom 25. August 2000 ist nicht geeignet, irgendwelche Anstrengungen der Behörden zu belegen. Allerdings beträgt der Zeitraum zwischen dem 11. August 2000 und dem Haftrichtertermin lediglich rund sechs Wochen. Die Behörden planen laut Haftverlängerungsantrag eine begleitete Ausschaffung des Beschwerdeführers in seine Heimat. Dies nimmt erfahrungsgemäss einige Zeit in Anspruch, vor allem auch im Hinblick auf das ferne Ziel. Unter diesen Umständen kann den Behörden auf den Haftrichtertermin vom 21. September 2000 hin (vgl. E. 1) noch kein Verstoss gegen das Beschleunigungsgebot vorgeworfen werden.
c) Der Beschwerdeführer macht erstmals vor dem Bundesgericht geltend, eine Ausschaffung in die Demokratische Republik Kongo sei zurzeit nicht möglich. Es bestehe keine Flugverbindung nach Kinshasa. Mit dieser Begründung habe die Fremdenpolizei des Kantons Zürich am 22. September 2000 einen Landsmann des Beschwerdeführers aus der Haft entlassen (vgl. act. 1 S. 3 Ziff. 2 und den entsprechenden Entlassungsrapport der Kantonspolizei Zürich vom 21. September 2000, in act. 3). Die Fremdenpolizei hat in ihrer Vernehmlassung hiezu nicht Stellung genommen. Im Übrigen wiederholt der Beschwerdeführer seinen Einwand, im Falle der Ausschaffung sei er in seiner Heimat an Leib und Leben gefährdet.
Der Umstand allein, dass die Ausreise nur schwer organisiert werden kann, lässt die Haft nicht bereits dahinfallen oder die Ausschaffung als undurchführbar erscheinen.
Gerade wegen solcher Schwierigkeiten und Ungewissheiten hat der Gesetzgeber die Haftdauer erheblich erhöht und die Möglichkeit der Haftverlängerung geschaffen (BBl 1994 I 305 ff.
S. 316). Die Haft ist gestützt auf Art. 13c Abs. 5 lit. a (2. Halbsatz) ANAG, weil unverhältnismässig, nur dann aufzuheben, wenn für die Undurchführbarkeit des Vollzugs der Entfernungsmassnahme triftige Gründe sprechen oder praktisch feststeht, dass sich die Ausschaffung innert der gesetzlichen Frist kaum wird realisieren lassen (<ref-ruling> E. 2 S. 220, 377 E. 5 S. 384; <ref-ruling> E. 3 S. 152 f.). Dies ist in der Regel nur 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 ausgeschlossen erscheint. Zu denken ist etwa an eine längerdauernde Transportunfähigkeit aus gesundheitlichen Gründen bzw. an eine ausdrückliche oder zumindest klar erkennbare und konsequent gehandhabte Weigerung eines Staates, gewisse Staatsangehörige zurückzunehmen (<ref-ruling> E. 2 S. 220; Alain Wurzburger, a.a.O., S. 330 f.). Als rechtliche Gründe können der Ausschaffung das Gebot des Non-refoulements oder eine Unzumutbarkeit des Vollzugs entgegenstehen, weil der Ausländer im Heimatstaat einer konkreten Gefährdung ausgesetzt wäre (Art. 14a Abs. 3 und 4 ANAG). Diesbezüglich sind die Prüfungspflichten des Haftrichters allerdings beschränkt:
Gegenstand seines Verfahrens bildet ausschliesslich die Rechtmässigkeit und Angemessenheit der Ausschaffungshaft als solcher (vgl. Art. 13c Abs. 2 ANAG), indessen nicht auch die Asyl- und Wegweisungsfrage; über diese entscheiden die zuständigen ausländerrechtlichen Behörden an sich abschliessend und verbindlich (vgl. Art. 100 Abs. 1 lit. b Ziff. 4 und 5 OG). Der Haftrichter hat die Haftgenehmigung deshalb nur zu verweigern, wenn sich der zu sichernde Wegweisungsentscheid als offensichtlich unzulässig erweist (vgl.
<ref-ruling> E. 2 S. 220; <ref-ruling> E. 2c S. 62). Die Frage, ob eine Wegweisung wegen nachträglich veränderter Umstände unzumutbar geworden sein könnte, bildet nicht Gegenstand der Prüfung im Haftverfahren. In solchen Situationen ist auf dem Rechtsmittelweg oder wiedererwägungsweise an die für die Wegweisung zuständigen (Asyl-)Behörden zu gelangen (<ref-ruling> E. 2 S. 221, mit Hinweisen).
Dass der Wegweisungsentscheid offensichtlich unzulässig wäre, ergibt sich hier nicht. In einer Mitteilung vom 21. Juni 2000 gab auch das Hochkommissariat der Vereinten Nationen für die Flüchtlinge (UNHCR) an, dass dem Beschwerdeführer im Heimatstaat keine Verfolgung drohe. Aufgrund des vom Beschwerdeführer vorgelegten Dokumentes vom 21. September 2000 zur Entlassung eines Landsmannes ist aber höchst fraglich, ob die Ausschaffung vollzogen werden kann. Von diesem Vorgang mag der Haftrichter zwar keine Kenntnis gehabt haben. Es ist augenscheinlich, dass auch der Beschwerdeführer hiervon erst nach dem Haftverlängerungstermin erfahren hat. Der Fremdenpolizei musste dieser Umstand damals hingegen wohl bekannt gewesen sein. Er betrifft die rechtliche Frage, ob der Vollzug der Ausweisung rechtlich oder tatsächlich durchführbar war. Das hatte der Haftrichter zu prüfen.
Aufgrund der Unkenntnis der im Entlassungsrapport angegebenen Begründung hatte er aber keine Gelegenheit, dies bisher in geeigneter Weise zu tun. Im Hinblick darauf ist dieser Umstand im vorliegenden Verfahren nicht als neues tatsächliches Vorbringen auszuschliessen (vgl. E. 1).
d) Nachdem der Haftrichter die Haftbedingung der rechtlichen und tatsächlichen Durchführbarkeit der Ausschaffung aufgrund ungenügender Information nicht umfassend überprüfen konnte, ist vorliegend angezeigt, die Sache an ihn zwecks erneuter Prüfung der Haftverlängerung zurückzuweisen.
Hierzu wird er nötigenfalls eine Auskunft des Bundesamtes für Flüchtlinge einzuholen haben. Im Rahmen der gleichzeitig anzustellenden Prüfung der weiteren Haftvoraussetzungen (insbes. des Beschleunigungsgebots) werden auch die seit dem 21. September 2000 aufgetretenen Änderungen, u.a. die näheren Umstände des Ausschaffungsversuchs vom 9. Oktober 2000, zu untersuchen sein, die sich aus den dem Bundesgericht vorgelegten Akten nur unvollständig ergeben.
Die Fremdenpolizei hatte ihren Verlängerungsantrag vom 20. September 2000 noch mit der Begründung der zeitintensiven Organisation einer begleiteten Rückschaffung begründet.
Die Massnahme vom 9. Oktober 2000 war dann aber ohne Begleitung geplant, was offenbar auch zu deren Scheitern führte.
5.- a) Nach dem Gesagten ist die Beschwerde gutzuheissen, soweit es um die Haftverlängerung geht, der angefochtene Entscheid aufzuheben und die Sache gestützt auf Art. 114 Abs. 2 OG zu erneuter Beurteilung - Prüfung der Durchführbarkeit der Ausschaffung sowie des gegenwärtigen Standes der Haftvoraussetzungen - an den Haftrichter zurückzuweisen.
Dieser wird umgehend, spätestens innerhalb von acht Arbeitstagen (analog zu Art. 13c Abs. 4 Satz 2 ANAG) ab Eröffnung dieses Urteils zu befinden haben. Eine Haftentlassung des Beschwerdeführers scheidet angesichts der unsicheren Aktenlage aus; diesbezüglich ist die Beschwerde abzuweisen.
b) Bei diesem Verfahrensausgang rechtfertigt sich, keine bundesgerichtlichen Kosten zu erheben (Art. 156 Abs. 1 und 2 OG). Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege wird damit gegenstandslos. Parteientschädigungen sind nicht zuzusprechen; der Beschwerdeführer war vor Bundesgericht nicht anwaltlich vertreten und hat auch keine Entschädigung verlangt.

Demnach erkennt das Bundesgericht:
1.- a) Die Verwaltungsgerichtsbeschwerde wird teilweise gutgeheissen, der angefochtene Entscheid aufgehoben und die Sache zu neuem Entscheid im Sinne der Erwägungen an den Haftrichter zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
b) Der Haftrichter am Bezirksgericht Zürich hat innert acht Arbeitstagen ab Eröffnung dieses Urteils aufgrund einer mündlichen Verhandlung über die Verlängerung der Ausschaffungshaft neu zu entscheiden.
2.- Es werden keine Kosten erhoben.
3.- Das Gesuch um unentgeltliche Rechtspflege wird als gegenstandslos abgeschrieben.
4.- Dieses Urteil wird dem Beschwerdeführer, der Fremdenpolizei des Kantons Zürich, dem Bezirksgericht Zürich, Haftrichteramt, dem Bundesamt für Ausländerfragen sowie dem Bundesamt für Flüchtlinge schriftlich mitgeteilt.
_
Lausanne, 1. November 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident: Der Gerichtsschreiber: