gemäss Art. 13b Abs. 2 ANAG, hat sich ergeben:
A.- Der 1969 geborene, nach eigenen Angaben im Libanon als palästinensischer Flüchtling aufgewachsene X._ reiste am 9. Juni 1999 in die Schweiz ein und ersuchte tags darauf um Asyl. Mit Verfügung vom 26. November 1999 lehnte das Bundesamt für Flüchtlinge das Asylgesuch ab und wies X._ aus der Schweiz weg. Die dagegen erhobene Beschwerde wies die Schweizerische Asylrekurskommission mit Entscheid vom 22. Januar 2000 ab. Das Bundesamt für Ausländerfragen belegte X._ am 12. November 1999 mit einer bis zum 11. November 2001 gültigen Einreisesperre. Diese Verfügung konnte ihm jedoch vorderhand nicht zugestellt werden.
In der Folge reiste X._ - gemäss eigenen Angaben - nach Italien aus und Ende März 2000 illegal wieder in die Schweiz ein. Am 6. April 2000 hielt ihn die Stadtpolizei Bern an, und er wurde in Ausschaffungshaft genommen; tags darauf eröffnete ihm die Fremdenpolizei des Kantons Bern die Einreisesperre und ersuchte die libanesische Botschaft darum, ihm einen Laissez-Passer auszustellen. Mit Entscheid vom 10. April 2000 prüfte und genehmigte der Haftrichter 3 des Haftgerichts III Bern-Mittelland die Ausschaffungshaft.
Mit Entscheid vom 29. Juni (schriftliche Urteilsbegründung:
30. Juni) 2000 prüfte und genehmigte derselbe Haftrichter eine Haftverlängerung bis zum 6. Oktober 2000.
B.- Am 29. September 2000 führte der Haftrichter 4 des Haftgerichts Bern-Mittelland (im Folgenden: Haftrichter) eine Verhandlung betreffend Haftverlängerung durch. Mit Entscheid vom 4. Oktober 2000 genehmigte er eine Verlängerung der Ausschaffungshaft bis zum 17. November 2000.
Mit Schreiben vom 30. September 2000, d.h. noch vor Ausfällung des Entscheides betreffend Haftverlängerung, wandte sich X._ mit einem in arabischer Sprache verfassten Schreiben an das Bundesgericht. Die Eingabe wurde von Amtes wegen übersetzt. Der Beschwerdeführer führt aus, entweder er sterbe im Gefängnis oder werde freigelassen, denn er sei weder ein Verbrecher, noch ein Drogenhändler, noch ein Dieb; seine beiden Lungen seien krank, und die Krankheit sei gefährlich und ansteckend.
Die Fremdenpolizei des Kantons Bern sowie der Haftrichter beantragen, die Beschwerde abzuweisen. Der Beschwerdeführer hat sich nicht mehr zur Sache geäussert. Das Bundesamt für Ausländerfragen hat sich nicht vernehmen lassen.

Das Bundesgericht zieht in Erwägung:
1.- a) Die Verwaltungsgerichtsbeschwerde hat die Begehren, deren Begründung mit Angabe der Beweismittel und die Unterschrift des Beschwerdeführers oder seines Vertreters zu enthalten (Art. 108 Abs. 2 OG). Sie muss sich sachbezogen mit dem angefochtenen Entscheid auseinander setzen (<ref-ruling> ff.). Bei Laienbeschwerden gegen die Genehmigung der Ausschaffungshaft stellt das Bundesgericht indessen keine hohen Anforderungen an die Beschwerdebegründung (vgl.
BGE 122 I 275 E. 3b S. 277). Ist daraus ersichtlich, dass sich der Betroffene - wie hier - (zumindest auch) gegen seine Haft wendet, nimmt es entsprechende Eingaben als Verwaltungsgerichtsbeschwerden entgegen.
b) Der Beschwerdeführer hat seine Beschwerde zwar verfrüht, d.h. vor der Ausfällung eines anzufechtenden Entscheids, verfasst. Aufgrund der Umstände ist hingegen klar, dass sich die - im Anschluss an die Haftverhandlung verfasste - Eingabe gegen einen allfälligen Haftbelassungsentscheid richten sollte; die verfrühte Einreichung soll daher dem nicht rechtskundigen Beschwerdeführer nicht zum Nachteil gereichen, und sein Schreiben ist als Beschwerde gegen den Haftentscheid vom 4. Oktober 2000 zu behandeln.
2.- Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen bzw. in dieser belassen, wenn 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. 2a S. 61), dessen Vollzug (z.B. wegen fehlender Reisepapiere) noch nicht möglich, jedoch absehbar ist. Zudem muss einer der in Art. 13b Abs. 1 ANAG genannten Haftgründe bestehen (<ref-ruling> E. 1 S. 3), die Ausschaffung rechtlich und tatsächlich möglich sein (Art. 13c Abs. 5 lit. a ANAG; vgl. <ref-ruling> E. 3 S. 152 ff.) und die Papierbeschaffung mit dem nötigen Nachdruck verfolgt werden (Art. 13b Abs. 3 ANAG; Beschleunigungsgebot; <ref-ruling> ff.). Die Haft darf höchstens drei Monate dauern; stehen dem Vollzug der Wegweisung 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.- a) Das Bundesamt für Flüchtlinge hat den Beschwerdeführer am 26. November 1999 aus der Schweiz weggewiesen.
Dem Vollzug dieses Wegweisungsentscheides steht als besonderes Hindernis entgegen, dass die Nationalität des Beschwerdeführers nach wie vor nicht geklärt ist. Der Haftgrund der Untertauchensgefahr (Art. 13 b 1 lit. c ANAG) ist gegeben:
Der Beschwerdeführer reiste, nachdem er die Schweiz verlassen hatte, illegal wieder ein, weshalb er keine Gewähr dafür bot, dass er sich für den Vollzug der Ausschaffung zur Verfügung halten würde (vgl. <ref-ruling> E. 2a S. 50/51).
b) Dem Beschleunigungsgebot sind die Behörden nachgekommen:
Schon am 7. April 2000 wandte sich die Fremdenpolizei an die libanesische Botschaft mit dem Ersuchen um Ausstellung eines Laissez-Passer für den Beschwerdeführer.
Am 12. April 2000 wurde der Beschwerdeführer auf der libanesischen Botschaft vorgeführt, wo er erklärte, Palästinenser zu sein. Die Botschaft soll sich daraufhin überlegt haben, ob sie das Schreiben um Ausstellung eines Reisepapiers überhaupt weiterleiten wolle. Es folgten zwei Anfragen (3. und
10. Mai 2000) bei der libanesischen Botschaft, die zu keinem Resultat führten. Am 16. Mai 2000 befragte der Spezialdienst der Fremdenpolizei X._ unter Mithilfe einer Übersetzerin, wobei diese offenbar festgestellt hat, dass der Beschwerdeführer akzentfrei libanesisch spricht.
Mit Schreiben vom 24. Mai 2000 ersuchte die Fremdenpolizei das Bundesamt für Flüchtlinge um Vollzugsunterstützung; am 23. Juni 2000 wandte sie sich an die UNWRA in Beirut zwecks weiterer Identitätsabklärungen. Mit Schreiben vom 5. Juli 2000 teilte die UNWRA Beirut mit, der Beschwerdeführer sei bei ihnen nicht als palästinischer Flüchtling registriert. Am 24. Juli 2000 befragte die Fremdenpolizei den Beschwerdeführer erneut, wobei dieser darauf beharrte, ein palästinensischer Flüchtling zu sein. Mit Schreiben vom 26. Juli 2000 bat die Fremdenpolizei das Bundesamt für Flüchtlinge nochmals um Vollzugsunterstützung; am 12. September 2000 ersuchte sie das Bundesamt um Informationen über das weitere Vorgehen; dieses erklärte am 19. September 2000, es habe sich am 10. August 2000 noch einmal an die libanesische Botschaft gewandt; eine Antwort aus Beirut sei bisher nicht eingegangen. Damit haben die kantonalen Behörden das unternommen, was von ihnen im Hinblick auf die Identifikation des Beschwerdeführers unternommen werden konnte; dass sich die libanesischen Behörden mit den ihnen obliegenden Abklärungen Zeit lassen, kann jedenfalls nicht den Behörden angelastet werden. Falls der Beschwerdeführer tatsächlich ein Libanese - und nicht ein palästinensischer Flüchtling - sein sollte, hätte er es übrigens sich selber zuzuschreiben, dass vorerst in einer falschen Richtung nachgeforscht worden ist.
c) Die Identität des Beschwerdeführers ist noch nicht geklärt. Es kann aber nicht gesagt werden, der Vollzug der Wegweisung sei deshalb rechtlich oder tatsächlich unmöglich, liegen doch keine konkreten Anzeichen dafür vor, dass sich der Libanon konsequent weigern würde, einen Staatsangehörigen oder einen auf seinem Gebiet aufgewachsenen palästinensischen Flüchtling zurückzunehmen.
d) Der Beschwerdeführer hat schon am 29. September 2000 vor dem Haftrichter geltend gemacht, er habe eine gefährliche ansteckende Lungenkrankheit; er wiederholt dies in seiner Beschwerde.
Unter Umständen fragt sich, ob aufgrund des Krankheitszustands - physischer oder psychischer Art - des Ausländers eine Ausschaffung überhaupt noch zumutbar und zulässig ist (vgl. Art. 14a ANAG und Art. 3 EMRK). Auch ein schlechter Gesundheitszustand kann in ausserordentlichen Fällen zur Unzumutbarkeit der Ausschaffung führen. Ist die Zumutbarkeit der Ausschaffung aufgrund des Gesundheitszustands zu verneinen, hat dies zur Folge, dass für die Anordnung oder Verlängerung von Ausschaffungshaft gar kein Raum mehr besteht. In besonderen Fällen kann die Verhältnismässigkeit der Ausschaffungshaft auch fraglich sein, wenn zwar nicht bleibende Unzumutbarkeit der Ausschaffung vorliegt, wohl aber vorübergehende Unzumutbarkeit oder Transportunfähigkeit von einer Dauer, welche die maximale Haftdauer von vornherein übersteigt (vgl. unveröffentlichtes Urteil vom 29. August 1997 i.S. Hassouna, E. 1b).
Der Haftrichter hat die Ausschaffungshaft nicht um die maximal noch zulässigen drei Monate, sondern nur bis zum 17. November 2000 verlängert. Während dieser Zeit sollte es möglich sein, abzuklären, ob die angebliche Krankheit des Beschwerdeführers einer Ausschaffung innerhalb der noch zulässigen maximalen Haftdauer entgegensteht. Diesfalls wäre der Beschwerdeführer sofort aus der Haft zu entlassen.
Handelt es sich hingegen um eine Krankheit, die zwar eine Ausschaffung nicht ausschliesst, welche aber die Hafterstehungsfähigkeit im Gefängnis für eine gewisse Zeitdauer wesentlich beeinträchtigt, so wäre die Haft z.B. in einer Krankenstation oder einem Spital zu vollziehen.
Insgesamt erweist sich im jetzigen Zeitpunkt die Verlängerung der Ausschaffungshaft als mit dem Bundesrecht vereinbar.
4.- a) Die Verwaltungsgerichtsbeschwerde ist nach dem Gesagten abzuweisen. Bei diesem Verfahrensausgang wären die Gerichtskosten grundsätzlich dem Beschwerdeführer aufzuerlegen (Art. 156 Abs. 1 OG). Im vorliegenden Fall ist jedoch wegen offensichtlicher Uneinbringlichkeit von der Erhebung einer Gerichtsgebühr abzusehen.
b) Die Fremdenpolizei des Kantons Bern wird ersucht, sicherzustellen, dass das vorliegende Urteil dem Beschwerdeführer korrekt eröffnet und nötigenfalls verständlich gemacht wird.

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Es werden keine Kosten erhoben.
3.- Dieses Urteil wird dem Beschwerdeführer, der Fremdenpolizei der Stadt Bern, dem Haftgericht III Bern-Mittelland (Haftrichter 4) und dem Bundesamt für Ausländerfragen schriftlich mitgeteilt.
_
Lausanne, 13. Oktober 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Die Gerichtsschreiberin: