Sachverhalt: A. A.a. A._ (Mieter, Beschwerdeführer) bewohnt seit dem 20. November 2013 eine 3-Zimmer-Wohnung in Basel. Diese wurde ihm vom Kanton Basel-Stadt (Vermieter, Beschwerdegegner) zur Verfügung gestellt. Die Parteien schlossen mehrere befristete Mietverträge über die Wohnung ab: Im ersten Vertrag überliess der Vermieter dem Mieter die Wohnung bis Ende März 2014, im zweiten bis Ende Juni 2014, im dritten bis Ende September 2014 und im vierten bis Ende November 2014. Nach Ablauf dieses Vertrages bot der Vermieter dem Mieter einen weiteren Vertrag bis Ende März 2015 an; der Mieter unterzeichnete die Vereinbarung jedoch nicht. Mit Schreiben vom 13. Januar 2015 wies der Vermieter den Mieter darauf hin, dass das Mietverhältnis Ende November 2014 abgelaufen sei und aktuell kein Vertrag mehr bestehe. A.b. Mit Gesuch vom 12. Mai 2015 beantragte der Vermieter beim Zivilgericht Basel-Stadt die Ausweisung des Mieters. Am 14. August 2015 fand eine mündliche Verhandlung statt. Mit Entscheid vom gleichen Tag wies das Zivilgericht Basel-Stadt den Mieter an, die Mietwohnung bis spätestens 28. August 2015, 12.00 Uhr, zu verlassen, ansonsten auf Antrag des Vermieters die Räumung vollzogen werde. Auf Gesuch des Mieters wurde der Entscheid schriftlich begründet. A.c. Gegen den Ausweisungsbefehl legte der Mieter ein kantonales Rechtsmittel beim Appellationsgericht Basel-Stadt ein, das dieses als Berufung entgegen nahm. A.d. Mit Entscheid vom 18. September 2015 wies das Appellationsgericht des Kantons Basel-Stadt die Berufung ab. Es wies das Gesuch um Gewährung der unentgeltlichen Rechtspflege wegen Aussichtslosigkeit des Rechtsmittels ab und auferlegte dem Berufungskläger die Kosten. B. Mit Beschwerde in Zivilsachen, eventuell subsidiärer Verfassungsbeschwerde, stellt der Mieter folgende Anträge: "1. Es seien die Entscheide des Appellationsgerichts Basel-Stadt vom 18. September 2015 und desjenigen des Zivilgerichts Basel-Stadt vom 14. August 2015 aufzuheben. 2. Es sei auf das Ausweisungsbegehren der SHB vom 12. Mai 2015 nicht einzutreten. Eventualiter sei dieses abzuweisen. 3. Es sei das Appellationsgericht Basel-Stadt anzuweisen, A._ für das vorinstanzliche Verfahren die unentgeltliche Rechtspflege mit dem Unterzeichner als Rechtsbeistand zu gewähren." Ausserdem ersucht der Beschwerdeführer um Gewährung der aufschiebenden Wirkung und um unentgeltliche Rechtspflege für das Verfahren vor Bundesgericht. Er rügt eine Verletzung von Art. 257 ZPO und macht im Wesentlichen geltend, er habe aufgrund einer öffentlich-rechtlichen Beziehung mit dem Kanton bzw. dessen Sozialamt einen Anspruch auf Nutzung der 3-Zimmer-Wohnung. Ausserdem beruft er sich auf Art. 12 und Art. 29 BV sowie Art. 8 und Art. 13 EMRK. Schliesslich rügt er eine Verletzung von Art. 117 ZPO und erklärt, sämtliche Rügen seien auch im Rahmen einer allfälligen subsidiären Verfassungsbeschwerde zu beurteilen. Auf die Einholung von Vernehmlassungen zur Beschwerde wurde verzichtet. C. Mit Verfügung vom 25. November 2015 wurde der Beschwerde die aufschiebende Wirkung erteilt. Nachdem der Beschwerdeführer weitere Unterlagen zur Bedürftigkeit eingereicht hat, ist die Sache spruchreif.