Sachverhalt:
A.
A._ (Mieter, Beschwerdeführer) schloss am 18. März 2015 mit der B._ AG (Vermieterin, Beschwerdegegnerin) einen Mietvertrag über eine 1 1/2-Zimmerwohnung in U._ ab. Am 26. Februar 2018 kündigte die Vermieterin den Mietvertrag mit Wirkung auf den 31. Mai 2018.
B.
B.a. Die Vermieterin reichte am 13. Juni 2018 beim Zivilgericht Basel-Stadt ein Gesuch um Ausweisung im Verfahren um Rechtsschutz in klaren Fällen ein.
Mit Verfügung vom 15. Juni 2018 forderte das Zivilgericht den Mieter auf, zum Gesuch der Vermieterin Stellung zu nehmen. Die Verfügung wurde an die Adresse des Mietobjekts gesandt und von der Post nach Ablauf der 7-tägigen Abholfrist als nicht abgeholt an das Gericht retourniert. Ein Zustellversuch per Gerichtsweibel scheiterte, woraufhin die Verfügung im Kantonsblatt publiziert wurde.
Nach unbenutztem Ablauf der Frist zur Stellungnahme wies das Zivilgericht den Mieter mit Entscheid vom 23. Juli 2018 an, die bei der Vermieterin gemieteten Räumlichkeiten bis spätestens am 6. August 2018, 11:30 Uhr, vollständig geräumt und einwandfrei gereinigt zu verlassen und die Schlüssel der Vermieterin auszuhändigen (Ziffer 1). Sodann wurde festgehalten, dass auf Antrag der Vermieterin ohne Weiteres und nach Bezahlung des Kostenvorschusses die Räumung vollzogen werde, wenn der Mieter nicht innert der gesetzten Frist ausgezogen sei (Ziffer 2). Im Weiteren auferlegte das Zivilgericht die Gerichtskosten von Fr. 600.-- dem Mieter und wies ihn an, der Vermieterin den von ihr geleisteten Kostenvorschuss von Fr. 400.-- zu ersetzen (Ziffer 3).
B.b. Dagegen erhob der Mieter Beschwerde an das Appellationsgericht des Kantons Basel-Stadt. Dieses hob mit Entscheid vom 8. Oktober 2018 in teilweiser Gutheissung der Beschwerde den erstinstanzlichen Kostenentscheid auf. Es auferlegte die Gerichtskosten des erstinstanzlichen Verfahrens von Fr. 600.-- der Vermieterin. Im Übrigen trat es auf die Beschwerde nicht ein und wies das Gesuch um unentgeltliche Rechtspflege für das Beschwerdeverfahren ab.
C.
Gegen den Entscheid des Appellationsgerichts erhob der Beschwerdeführer Beschwerde an das Bundesgericht. Er beantragt, es sei der Entscheid des Appellationsgerichts, mit Ausnahme der Verlegung der Kosten der ersten Instanz, und der Entscheid des Zivilgerichts vollumfänglich aufzuheben. Es sei nicht auf das Ausweisungsgesuch einzutreten. Eventualiter sei der Entscheid des Appellationsgerichts, mit Ausnahme der Verlegung der Kosten der ersten Instanz, und der Entscheid des Zivilgerichts vollumfänglich aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Es seien die Gerichtskosten der Vorinstanz der Beschwerdegegnerin aufzuerlegen. Es sei ihm schliesslich für das Verfahren vor der Vorinstanz wie für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege zu gewähren.

Erwägungen:
1.
1.1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2.1 mit Hinweisen).
1.2. Der Beschwerdeführer beantragt die Aufhebung des erstinstanzlichen Entscheids. Darauf kann nicht eingetreten werden, denn die Beschwerde in Zivilsachen und die subsidiäre Verfassungsbeschwerde sind nur gegen Entscheide letzter kantonaler Instanzen zulässig (<ref-law>, <ref-law>).
1.3. Der Streitwert beträgt Fr. 6'600.-- und erreicht damit die Streitwertgrenze für eine Beschwerde in Zivilsachen nicht. Die Beschwerde in Zivilsachen ist in diesem Fall dennoch zulässig, wenn sich eine Rechtsfrage von grundsätzlicher Bedeutung stellt (<ref-law>).
Der Beschwerdeführer beruft sich zwar darauf, dass sich Rechtsfragen von grundsätzlicher Bedeutung stellten und seine Beschwerde als Beschwerde in Zivilsachen anhand zu nehmen sei. Er macht aber nur die Verletzung von verfassungsmässigen Rechten geltend. Damit kann offen bleiben, ob das Rechtsmittel als Beschwerde in Zivilsachen oder als subsidiäre Verfassungsbeschwerde entgegen zu nehmen ist. Das ist im vorliegenden Fall im Ergebnis unerheblich, weil die Kognition des Bundesgerichts bei verfassungsmässigen Rechten so oder anders die gleiche ist:
Es gilt eine qualifizierte Rügepflicht und das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (<ref-law>; <ref-law>; <ref-ruling> E. 1.4; <ref-ruling> E. 1.3.1). Unerlässlich ist, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von verfassungsmässigen Rechten liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als verfassungswidrig erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 89, 115 E. 2 S. 116). Soweit die Beschwerdeschrift diesen Begründungsanforderungen nicht genügt, so ist darauf nicht einzutreten (BGE <ref-ruling> E. 1.3.1).
2.
Die Vorinstanz erwog, der Beschwerdeführer habe im Zeitpunkt der Einreichung des Ausweisungsgesuchs die Wohnung bereits vollständig geräumt und einwandfrei gereinigt verlassen. Die Schlüssel hätten sich im Herrschaftsbereich der Beschwerdegegnerin befunden. Der Beschwerdeführer habe daher kein aktuelles und praktisches Interesse an der Aufhebung oder Änderung der Dispositivziffern 1 und 2 des Ausweisungsentscheids. Die Voraussetzungen für einen ausnahmsweisen Verzicht auf die Aktualität des Rechtsschutzinteresses seien nicht erfüllt. Folglich sei auf die Beschwerde gegen den Ausweisungsentscheid mangels eines schutzwürdigen Interesses nicht einzutreten. Einzutreten sei aber auf die Beschwerde gegen den erstinstanzlichen Kostenentscheid.
Die Vorinstanz kam bezüglich dem Kostenentscheid zum Schluss, dass die Verfügung der Erstinstanz vom 15. Juni 2018 dem Beschwerdeführer nie zugestellt worden sei. Die Publikation im Kantonsblatt habe keine Zustellung bewirkt, da die Voraussetzungen für eine öffentliche Bekanntmachung nicht erfüllt gewesen seien. Die Erstinstanz habe dem Beschwerdeführer daher keine Möglichkeit zur Äusserung zum Ausweisungsgesuch der Beschwerdegegnerin gewährt und die Behauptungen der Beschwerdegegnerin zu Unrecht als unbestritten ihrem Entscheid zugrunde gelegt. Damit habe die Erstinstanz den Anspruch des Beschwerdeführers auf rechtliches Gehör verletzt.
Schwerwiegende Verfahrensmängel vor der ersten Instanz stellten regelmässig einen Rückweisungsgrund dar. Im vorliegenden Fall könne jedoch ausnahmsweise ein reformatorischer Kostenentscheid gefällt werden. Da der Zweck des Ausweisungsgesuchs im Zeitpunkt seiner Einreichung bereits vollständig erfüllt gewesen sei, hätte die Erstinstanz darauf mangels Rechtsschutzinteresses nicht eintreten dürfen. Bei einem Nichteintretensentscheid würden die Prozesskosten der Beschwerdegegnerin als Gesuchstellerin auferlegt. Die Gerichtskosten des erstinstanzlichen Verfahrens seien folglich von der Beschwerdegegnerin zu tragen.
Im erstinstanzlichen Verfahren sei der Beschwerdeführer nicht anwaltlich vertreten gewesen. Er habe seinen Rechtsvertreter erst für das Ersuchen um schriftliche Begründung des angefochtenen Entscheids beigezogen und stellte erst darin ein Gesuch um unentgeltliche Rechtspflege. Folglich komme für das erstinstanzliche Verfahren weder eine Parteientschädigung noch die unentgeltliche Verbeiständung in Betracht. Für das kantonale Beschwerdeverfahren sei das Gesuch um unentgeltliche Rechtspflege abzuweisen.
3.
3.1. Dagegen beanstandet der Beschwerdeführer eine Verletzung von <ref-law> und Art. 6 Ziff. 1 EMRK. Ihm sei die Möglichkeit genommen worden, sich zum Rechtsschutzinteresse der Beschwerdegegnerin zu äussern und damit das umgehende Nichteintreten der ersten Instanz zu veranlassen. Es frage sich, ob die Verletzung des rechtlichen Gehörs nicht für sich selbst ein Rechtsschutzinteresse an einer materiellen Beurteilung begründen vermöge. Ihm sei der Zugang zur ersten Instanz zunächst durch die mangelnde Zustellung des Gesuchs durch die erste Instanz verwehrt worden. Hernach sei ihm der Zugang zur ersten Instanz oder generell zu einer richterlichen Beurteilung durch die Vorinstanz dahingehend verweigert worden, dass diese mangels Rechtsschutzinteresse nicht auf die materiellen Vorbringen eingetreten sei. Die Vorinstanz habe auch keine Rückweisung an die erste Instanz vorgenommen, sondern selbst einen materiellen Entscheid getroffen. Die Vorinstanz habe das aktuelle praktische Interesse dahingehend angewandt, dass dem Beschwerdeführer der Zugang zu einer gerichtlichen Beurteilung gänzlich verwehrt geblieben sei. Es handle sich folglich um eine formelle Rechtsverweigerung, da der Standpunkt des Beschwerdeführers von keiner Instanz gehört oder materiell beurteilt worden sei.
3.2. Es ist nicht richtig, wenn der Beschwerdeführer vorbringt, dass sein Standpunkt zur Ausweisung aus der Mietwohnung "von keiner Instanz" gehört worden und ihm der Zugang zu einer gerichtlichen Beurteilung "gänzlich verwehrt" geblieben sei. Die Vorinstanz ging ausführlich auf die Vorbringen des Beschwerdeführers zur Ausweisung aus der Wohnung ein (vorinstanzlicher Entscheid E. 1.2 S. 3 - 7). Sie kam aber zum Schluss, dass auf seine Beschwerde gegen den Ausweisungsentscheid mangels schutzwürdigen Interesses nicht eingetreten werden könne. Die Vorinstanz trat damit auf die Beschwerde gegen den Ausweisungsentscheid nicht ein, da es an einem schutzwürdigen Interesse und somit an einer Prozessvoraussetzung bzw. an der Beschwer fehlte. Es kann daher nicht von einer formellen Rechtsverweigerung gesprochen werden. Eine solche läge erst vor, wenn eine Behörde auf eine ihr frist- und formgerecht unterbreitete Sache nicht eintritt, obschon sie darüber befinden müsste (<ref-ruling> E. 2.1 S. 9). Vorliegend hatte die Vorinstanz aber über die Ausweisung aufgrund des Auszugs des Beschwerdeführers aus der Wohnung nicht mehr zu befinden und trat damit zu Recht auf die Beschwerde gegen den Ausweisungsentscheid nicht ein (vgl. <ref-ruling> E. 3.3; Urteil 4D_79/2015 vom 22. Januar 2016 E. 2.1 f. mit weiteren Hinweisen).
3.3. Auf das Erfordernis des aktuellen praktischen Interesses kann dann ausnahmsweise verzichtet werden, wenn sich die gerügte Rechtsverletzung jederzeit wiederholen könnte und eine rechtzeitige gerichtliche Überprüfung im Einzelfall kaum je möglich wäre (<ref-ruling> E. 1.1 S. 94; <ref-ruling> E. 1.1 S. 499; Urteil 4A_576/2014 vom 25. März 2015 E. 1.3.1; vgl. aber <ref-ruling> E. 1.3.1).
Bereits die Vorinstanz entschied, dass diese Voraussetzungen für die Beschwerde gegen den Ausweisungsentscheid nicht gegeben sind. Der Beschwerdeführer vermag keine Verletzung seiner verfassungsmässigen Rechte darzulegen, indem er lediglich vorträgt, dass die Vorinstanz auf das Erfordernis des aktuellen praktischen Interesses hätte verzichten sollen, weil er eine Verletzung seines rechtlichen Gehörs geltend machte. Ohnehin stellte die Vorinstanz im Zusammenhang mit der Beurteilung des erstinstanzlichen Kostenentscheids eine Verletzung des Anspruchs auf rechtliches Gehör durch die erste Instanz fest ( dazu oben Erwägung 2).
3.4. Es gelingt dem Beschwerdeführer auch nicht ein aktuelles Rechtsschutzinteresse darzulegen, indem er eventualiter ausführt, er erhielte einzig Erleichterung mit einem "materiellen (und nicht lediglich vorfrageweisen) Entscheid", der ausdrücklich festhielte, dass auf das Ausweisungsgesuch der Beschwerdegegnerin nicht hätte eingetreten werden dürfen. Nur mit einem solchen materiellen Entscheid sei er nicht mehr beschwert, als dass er einem potenziellen neuen Vermieter einen Entscheid vorlegen könnte, der aufzeige, dass er sich an die mietrechtliche Gesetzgebung und die sozialen Gepflogenheiten halte und kein Risiko für den Vermieter darstelle.
Die Vorinstanz stellte fest, dass der Beschwerdeführer die Wohnung im Zeitpunkt der Einreichung des Ausweisungsgesuchs vollständig geräumt habe, die Wohnung einwandfrei gereinigt gewesen sei und dass sich die Wohnungsschlüssel im Herrschaftsbereich der Beschwerdegegnerin befunden haben. Der Zweck des Ausweisungsgesuchs sei im Zeitpunkt seiner Einreichung bereits vollständig erfüllt gewesen, weshalb die Erstinstanz auf das Gesuch mangels Rechtsschutzinteresses nicht hätte eintreten dürfen.
Diese Erwägungen der Vorinstanz kann der Beschwerdeführer einem potenziellen Vermieter vorlegen. Warum er daneben bezüglich der Ausweisung einen "materiellen" Entscheid benötigte und die Vorinstanz auf die Beschwerde gegen den erstinstanzlichen Ausweisungsentscheid hätte eintreten und diese materiell beurteilen müssen, ist nicht erkennbar.
4.
4.1. Die Vorinstanz verweigerte dem Beschwerdeführer die unentgeltliche Rechtspflege für das Beschwerdeverfahren. Sie ging zunächst auf die Lebenshaltungskosten des Beschwerdeführers ein, da dieser in eine deutsche Enklave in der Schweiz gezogen war. Sie erwog, dass es durchaus möglich sei, dass der Beschwerdeführer aufgrund der niedrigen Lebenshaltungskosten in Deutschland den prozessualen Notbedarf wie auch die Prozesskosten decken könne. Die Vorinstanz führte aber anschliessend aus, dass der Verfahrensleiter dem Beschwerdeführer eine Frist angesetzt habe, um seine aktuellen finanziellen Verhältnisse und seine aktuellen Wohnverhältnisse detailliert darzulegen und soweit möglich zu belegen. Der anwaltlich vertretene Beschwerdeführer sei jedoch jegliche Angaben zu seinem Bedarf und seinen Wohnverhältnissen schuldig geblieben. Aus diesem Grund könne der konkrete monatliche Überschuss nicht bestimmt werden. Damit habe der Beschwerdeführer die zur Beurteilung seiner aktuellen wirtschaftlichen Situation nötige und zumutbare Mitwirkung trotz gerichtlicher Aufforderung verweigert. Seine Bedürftigkeit könne deshalb ohne weiteres verneint und das Gesuch um unentgeltliche Rechtspflege abgewiesen werden.
4.2. Die Vorinstanz verweigerte nach dem Gesagten dem Beschwerdeführer die unentgeltliche Rechtspflege, da dieser die Mitwirkungsobliegenheit verletzte. Danach obliegt es dem Beschwerdeführer als Gesuchsteller um unentgeltliche Rechtspflege, seine Einkommens- und Vermögensverhältnisse umfassend darzustellen und soweit möglich zu belegen (<ref-ruling> E. 4a S. 164 f.; <ref-ruling> E. 3a S. 181 f; Urteil 4A_44/2018 vom 5. März 2018 E. 5.3).
Es wäre damit am Beschwerdeführer, vor Bundesgericht aufzuzeigen, dass er entgegen den Feststellungen der Vorinstanz seiner Mitwirkungsobliegenheit im kantonalen Verfahren nachgekommen wäre oder die Vorinstanz die Voraussetzungen an die Mitwirkung überspannt hätte. Dies beanstandet er nicht. Vielmehr trägt er lediglich vor, dass <ref-law>, Art. 6 EMRK und Art. 14 Abs. 3 lit. d UNO-Pakt II verletzt seien, da die Erstinstanz ihm die unentgeltliche Rechtspflege unter Vorlage der Steuerverfügung gewährt habe, die Vorinstanz den Grundbedarf willkürlich nicht korrekt berechnet habe und die Lebenshaltungskosten bei einer deutschen Enklave nicht habe kürzen dürfen. Dies ist nicht zielführend. Seine Rüge geht damit fehl.
Unabhängig davon ist das Vorgehen der Vorinstanz nicht zu beanstanden: Die Vorinstanz setzte dem Beschwerdeführer aufgrund seiner speziellen Wohnsituation in einer deutschen Enklave in der Schweiz zu Recht Frist an, um aktuelle Angaben zu seinem konkreten Bedarf und seinen Wohnverhältnissen zu machen. Nachdem der durch einen Rechtsanwalt vertretene Beschwerdeführer dieser Aufforderung nicht nachkam, konnte die Vorinstanz das Gesuch mangels ausreichender Substantiierung oder mangels Bedürftigkeitsnachweises um unentgeltliche Rechtspflege abweisen.
5.
Der Beschwerdeführer verlangt schliesslich eine andere Verteilung der vorinstanzlichen "ordentlichen und ausserordentlichen Gerichtskosten". Er begründet dies aber nur, wenn überhaupt, für den Fall der Gutheissung seiner Beschwerde. Da die Beschwerde nach dem Ausgeführten nicht gutgeheissen werden kann, erübrigt sich auch eine andere Verteilung der Kostenfolgen des vorinstanzlichen Verfahrens.
6.
Der Beschwerdeführer vermag damit keine Verletzung von seinen verfassungsmässigen Rechten darzulegen. Die Beschwerde ist somit abzuweisen, soweit auf sie eingetreten werden kann.
Das Gesuch um Gewährung der unentgeltlichen Rechtspflege für das bundesgerichtliche Verfahren ist abzuweisen, weil die Beschwerde als von vornherein aussichtslos erscheint (<ref-law>). Dabei musste darüber unter den gegebenen Umständen nicht vorgängig separat entschieden werden (vgl. Urteil 4A_20/2011 vom 11. April 2011 E. 7.2.2).
Der Beschwerdegegnerin ist aus dem bundesgerichtlichen Verfahren kein entschädigungspflichtiger Aufwand erwachsen, weshalb ihr keine Parteientschädigung zuzusprechen ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 25. Januar 2019
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Brugger