Sachverhalt:
A.
A._, geboren 1964, stammt aus Sri Lanka und reiste am 19. August 1998 in die Schweiz ein. Vom 19. April bis 31. Oktober 1999 arbeitete er bei der B._ AG. Am 5. Noveber 1999 erlitt er einen ischämischen paramedianen Ponsinfarkt und ersuchte im Juli 2000 um Leistungen der Invalidenversicherung. Mit Verfügung vom 17. Oktober 2000 verneinte die IV-Stelle des Kantons Zürich einen Anspruch mangels Erfüllung der einjährigen Mindestbeitragszeit. Im Oktober 2001 meldete sich A._ erneut zum Leistungsbezug an, was die IV-Stelle am 20. November 2001 unter Verweis auf die Verfügung vom 17. Oktober 2000 ablehnte.
Mit Schreiben vom 3. März 2008 liess A._ das Gesuch um Abklärung seines IV-Grades stellen, da dessen Kenntnis notwendig sei für den Bezug von Zusatzleistungen. Die IV-Stelle holte daraufhin Berichte bei den behandelnden Ärzten sowie ein neurologisch-psychiatrisches Gutachten bei Frau Dr. med. C._, Fachärztin für Neurologie sowie für Psychiatrie und Psychotherapie, vom 2. September 2008 ein. Mit Schreiben vom 13. März 2009 teilte die IV-Stelle dem Amt für Zusatzleistungen mit, der Invaliditätsgrad betrage 60 % ab 1. März 2001. Im Dezember 2009 ersuchte A._ wiederum um eine Rente der Invalidenversicherung. Auf die Aufforderung der IV-Stelle, Unterlagen zum Beleg der veränderten tatsächlichen Verhältnisse seit Erlass der letzten Verfügung einzureichen, widersetzte er sich anfänglich, liess in der Folge aber Berichte der behandelnden Ärzte einreichen. Mit Verfügung vom 7. September 2010 lehnte die IV-Stelle das Leistungsgesuch erneut ab, da die Versicherungsvoraussetzungen bei Eintritt der Invalidität erfüllt sein müssten, was vorliegend nicht gegeben sei, und eine erneute Anmeldung keinen neuen Versicherungsfall begründe. Am 29. November 2011 liess A._ das Gesuch um Hilflosenentschädigung stellen. Die IV-Stelle erstellte einen Abklärungsbericht vom 16. Februar 2012. Mit Entscheid vom 2. Mai 2012 hiess das Sozialversicherungsgericht des Kantons Zürich die gegen die Verfügung vom 7. September 2010 erhobene Beschwerde in dem Sinne gut, dass es die Sache an die IV-Stelle zurückwies mit der Feststellung, die versicherungsmässigen Voraussetzungen nach <ref-law> seien erfüllt und die Verwaltung habe den Anspruch auf eine allfällige Invalidenrente für die Zeit nach November 2009 abzuklären und neu zu verfügen. Die IV-Stelle holte einen Verlaufsbericht bei der Hausärztin ein und ordnete mit Mitteilung vom 16. Januar 2013 eine polydisziplinäre medizinische Untersuchung an, wobei die Gutachterstelle bekannt gegeben werde, sobald sie bestimmt sei. Nachdem sich A._ einer polydisziplinären Untersuchung widersetzte, erliess die IV-Stelle am 5. Februar 2013 eine entsprechende Verfügung; das Sozialversicherungsgericht bestätigte diese am 31. Oktober 2013 und das Bundesgericht trat auf die dagegen erhobene Beschwerde mit Urteil 8C_12/2014 vom 3. Juli 2014 nicht ein. In der Folge unterzog sich A._ der polydisziplinären Begutachtung durch die MEDAS Ostschweiz (Gutachten vom 11. Dezember 2014). Am 27. März 2015 sprach ihm die IV-Stelle eine ganze Invalidenrente ab 1. Dezember 2009 zu; auf Gesuch hin ordnete sie am 22. April 2015 unter Aufhebung der Verfügung vom 27. März 2015 die Auszahlung der ganzen Invalidenrente an die zuständige Fürsorgestelle an.
Bereits am 28. Juni 2012 hatte die IV-Stelle den Anspruch auf eine Hilflosenentschädigung abgewiesen, was das Sozialversicherungsgericht mit Entscheid vom 20. Dezember 2013 und das Bundesgericht mit Urteil 8C_117/2014 vom 3. Juli 2014 bestätigten.
B.
Das Sozialversicherungsgericht wies die gegen die Verfügung vom 22. April 2015 erhobene Beschwerde am 7. September 2015 ab.
C.
A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Antrag, seine Invalidenrente sei ihm unter Aufhebung des vorinstanzlichen Entscheids bereits ab 20. Juli 2000, eventualiter ab 1. Oktober 2001, zu gewähren. Zudem ersucht er um unentgeltliche Rechtspflege.
Die IV-Stelle schliesst auf Abweisung der Beschwerde. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Die Beschwerde kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 1.4 S. 140). Gemäss <ref-law> ist die Beschwerde hinreichend zu begründen, andernfalls wird darauf nicht eingetreten (<ref-law>). Das Bundesgericht prüft grundsätzlich nur die geltend gemachten Rügen; es ist nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu prüfen, wenn diese vor Bundesgericht nicht mehr vorgetragen wurden. Es kann die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht nur insofern prüfen, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>).
1.2. Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Abs. 1). Es kann diese Sachverhaltsfeststellung von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Abs. 2). Die Voraussetzungen für eine Sachverhaltsrüge nach <ref-law> und für eine Berichtigung des Sachverhalts von Amtes wegen nach <ref-law> stimmen im Wesentlichen überein. Soweit es um die Frage geht, ob der Sachverhalt willkürlich oder unter verfassungswidriger Verletzung einer kantonalen Verfahrensregel ermittelt worden ist, sind strenge Anforderungen an die Begründungspflicht der Beschwerde gerechtfertigt. Entsprechende Beanstandungen sind vergleichbar mit den in <ref-law> genannten Rügen. Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Vielmehr ist in der Beschwerdeschrift nach den erwähnten gesetzlichen Erfordernissen darzulegen, inwiefern diese Feststellungen willkürlich bzw. unter Verletzung einer verfahrensrechtlichen Verfassungsvorschrift zustande gekommen sind. Andernfalls können Vorbringen mit Bezug auf einen Sachverhalt, der von den Feststellungen im angefochtenen Entscheid abweicht, nicht berücksichtigt werden. Vorbehalten bleiben offensichtliche Sachverhaltsmängel im Sinne von <ref-law>, die dem Richter geradezu in die Augen springen (<ref-ruling> E. 6.2 S. 288; <ref-ruling> E. 1.4.3 S. 255).
2.
Streitig ist der Beginn der Nachzahlung der Invalidenrente.
3.
Die Vorinstanz hat die Bestimmungen und Grundsätze über die Wiedererwägung (<ref-law>; <ref-ruling> E. 3.1 S. 79 mit Hinweisen) und die prozessuale Revision (<ref-law>; Urteil 9C_955/2012 vom 13. Februar 2013 E. 3.1 mit Hinweisen) zutreffend dargelegt. Darauf wird verwiesen.
4.
4.1. Das MEDAS-Gutachten vom 11. Dezember 2014 stellt kein neues Beweismittel im Sinne von <ref-law> dar. Denn Grund für die zuvor erfolgte Verneinung des Anspruchs war nicht die Unmöglichkeit des Nachweises einer Arbeitsunfähigkeit oder des Ausmasses der gesundheitlichen Einschränkungen, sondern die Verneinung der Versicherungsklausel, d.h. der erfüllten einjährigen Beitragspflicht bei Eintritt des Versicherungsfalls. Das MEDAS-Gutachten ist aber nicht geeignet, den Nachweis der erfüllten Beitragspflicht bei Eintritt des Versicherungsfalls zu erbringen. Es dient lediglich dazu, die gesundheitlichen Einschränkungen in ihrem aktuellen Ausmass festzustellen; denn dass eine allenfalls leistungsbegründende gesundheitliche Einschränkung vorliegt, war bereits aus den damaligen ärztlichen Berichten ersichtlich (vgl. die Berichte der Höhenklinik D._ vom 5. April 2000, der neurologischen Klinik, Spital E._, vom 2. Dezember 1999, sowie des Spitals F._ vom 5. Mai 2000, 31. Mai 2000 und 11. August 2000; vgl. dazu auch den Entscheid des Sozialversicherungsgerichts vom 2. Mai 2012 E. 4.2 und 4.3). Somit liegt keine prozessuale Revision nach <ref-law> vor, sondern eine Wiedererwägung nach <ref-law> (so bereits Entscheid des Sozialversicherungsgerichts vom 2. Mai 2012 E. 3.4 und 3.5).
4.2. Bei der Frage der Versicherungsklausel nach aArt. 6 Abs. 1 IVG (in der bis 31. Dezember 2000 geltenden Fassung) ist zweierlei zu prüfen: Erstens muss der Zeitpunkt des Eintritts des Versicherungsfalls, d.h. der Zeitpunkt des Vorliegens der für die jeweilige Leistungsart erforderlichen Invalidität, festgestellt werden; dabei handelt es sich um einen IV-spezifischen Aspekt. Zweitens ist zu prüfen, ob die betroffene Person zu diesem Zeitpunkt die Versicherteneigenschaft aufweist; dies stellt eine AHV-analoge Frage dar (Meyer, Bundesgesetz über die Invalidenversicherung, 1997, S. 34 f.; vgl. auch Meyer/ Reichmuth, Bundesgesetz über die Invalidenversicherung, 3. Aufl., 2014, N. 2 zu <ref-law>). Bei IV-spezifischen Aspekten beurteilt sich die Wirkung einer Wiedererwägung nach <ref-law>, d.h. ex nunc; bei AHV-spezifischen Punkten erfolgt die Beurteilung einer allfälligen Nachzahlung nach aArt. 85 Abs. 1 IVV (in Kraft bis 31. Dezember 2007) resp. <ref-law>, d.h. ex tunc (vgl. dazu <ref-ruling> und SVR 2012 IV Nr. 28 S. 116, 9C_409/2011). Zudem ist bei ausländischen Staatsangehörigen kumulativ erforderlich, dass sie ihren Wohnsitz und gewöhnlichen Aufenthalt in der Schweiz haben und entweder während mindestens eines vollen Jahres Beiträge geleistet oder sich ununterbrochen während zehn Jahren in der Schweiz aufgehalten haben (a<ref-law> in der bis 31. Dezember 2000 in Kraft gewesenen Fassung).
Im hier zu beurteilenden Fall bejahte das Sozialversicherungsgericht in seinem Entscheid vom 2. Mai 2012 die Erfüllung der Versicherungsklausel nach aArt. 6 Abs. 1 und 2 IVG, indem es - anders als die IV-Stelle, welche davon ausging, der Beschwerdeführer sei bereits bei seiner Einreise im Jahr 1998 invalide gewesen - den ischämischen paramedianen Ponsinfarkt vom 5. November 1999 als auslösendes Moment für den Beginn der Arbeitsunfähigkeit und damit für den Eintritt des Versicherungsfalls im Jahr 2000 erachtete; dabei stützte es sich auf ärztliche Berichte, welche - mit Ausnahme jenes der Frau Dr. med. G._, Fachärztin für Allgemeine Medizin, vom 8. Oktober 2001 - in den Jahren 1999 und 2000 erstattet wurden, folglich vor Erlass der ersten ablehnenden Verfügung vom 17. Oktober 2000. Demnach liegt die fälschliche Verneinung der erfüllten Versicherungsklausel in einem IV-spezifischen Aspekt (Eintritt der massgeblichen Invalidität) begründet (vgl. explizit Meyer, a.a.O., S. 35 und Meyer/ Reichmuth, a.a.O., N. 2 zu <ref-law>). Die Korrektur dieser Leistungsverweigerung richtet sich somit nach <ref-law>, d.h. es erfolgt eine Nachzahlung ex nunc. Damit ist aber noch nicht gesagt, ob die erneute Anmeldung von 2001 oder jene von 2009 massgebend ist.
4.3. Der Beschwerdeführer macht gestützt auf <ref-ruling> E. 6.4 S. 438 die Massgeblichkeit der Neuanmeldung von 2001 geltend. Dem kann nicht gefolgt werden, da jener Fall nicht auf den hier zu beurteilenden übertragbar ist: In <ref-ruling> ging es um eine geltend gemachte Veränderung des Gesundheitszustandes und damit um eine Leistungsvoraussetzung, welche variabel sein kann. Bei der Erfüllung der Versicherungsklausel handelt es sich hingegen um einen Umstand, welcher keiner Veränderungen unterliegt und - falls einmal verneint - in einem späteren Zeitpunkt bezüglich desselben Gesundheitsschadens nicht infolge des Zeitablaufs doch noch erfüllt werden kann. Somit könnte das erneute Leistungsgesuch nur dann als Auslöser für ein Tätigwerden von Amtes wegen gelten, sofern der Beschwerdeführer in seiner erneuten Anmeldung Gründe anführt, weshalb die Versicherungsklausel entgegen der ersten Verfügung doch erfüllt sei. Nach der Rechtsprechung kommt es bei der Beurteilung dieser Frage auf den Inhalt und die Formulierung des Wiedererwägungsgesuchs an (<ref-ruling> E. 4a S. 297); daran hat auch die Präzisierung von <ref-ruling> E. 6 S. 437 nichts geändert. Der Beschwerdeführer bringt in seiner erneuten Anmeldung von 2001 keine Gründe vor, weshalb die Versicherungsklausel entgegen der Verfügung vom 17. Oktober 2000 doch erfüllt wäre. Insofern bestand für die IV-Stelle kein Anlass, gestützt auf die erneute Anmeldung von 2001 die rechtskräftig verneinte Erfüllung der Versicherungsklausel nochmals zu prüfen. Damit ist nicht die Anmeldung von 2001 massgebend. Eine andere Auffassung im hier genannten Fall würde bedeuten, dass die Verwaltung bei einer Neuanmeldung stets auch die bereits rechtskräftig feststehenden und keiner durch Zeitablauf möglichen Veränderung zugänglichen Elemente von Amtes wegen einer Überprüfung zu unterziehen hätte. Dies geht nicht an.
4.4. Nach dem Gesagten haben Vorinstanz und Verwaltung zu Recht die Auszahlung der Invalidenrente gestützt auf <ref-law> erst ab Dezember 2009 bejaht.
5.
Dem Verfahrensausgang entsprechend sind die Gerichtskosten vom Beschwerdeführer als unterliegender Partei zu tragen (<ref-law>). Ihm ist indessen die unentgeltliche Rechtspflege zu gewähren (<ref-law>), weil die Bedürftigkeit aktenkundig und die Beschwerde nicht als aussichtslos zu bezeichnen ist sowie die anwaltliche Vertretung geboten war. Es ist indessen auf <ref-law> hinzuweisen, wonach der Gerichtskasse Ersatz zu leisten sein wird, wenn dies später möglich sein sollte.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt und Rechtsanwalt Philip Stolkin wird als unentgeltlicher Anwalt bestellt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Dem Rechtsvertreter des Beschwerdeführers wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
5.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 29. Februar 2016
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Riedi Hunold