Sachverhalt:
A.
A.a. Mit Verfügung vom 3. Oktober 2008 sprach die Kantonale IV-Stelle Wallis A._ nach erwerblichen und medizinischen Abklärungen, namentlich gestützt auf eine Untersuchung durch den Regionalen ärztlichen Dienst (RAD; Schlussbericht vom 27. November 2007), vom 1. April 2005 bis 31. Januar 2008 eine halbe Rente sowie ab 1. Februar 2008 eine Viertelsrente zu. Im Zuge eines Revisionsverfahrens verfügte die IV-Stelle am 30. August 2010 die Einstellung der Rente.
A.b. Am 21. November 2013 meldete sich A._ erneut bei der IV-Stelle zum Leistungsbezug an. Er gab an, unter Knieschmerzen (bei Operationen in den Jahren... und...), Rückenschmerzen (Operation...) sowie seit über 20 Jahren unter Depressionen zu leiden. Nach Eingang von Berichten des Spitals B._ vom 29. November, 12. und 17. Dezember 2013 sowie des Hausarztes Dr. med. C._, FMH Allgemeine Medizin, vom 10. Februar 2014, holte die IV-Stelle eine Beurteilung des RAD (Dr. med. D._, Allgemeine Medizin FMH) vom 3. März 2014 ein. Mit Vorbescheid vom 10. März 2014 stellte sie die Zusprechung einer Viertelsrente vom 1. August bis 31. Oktober 2013, einer ganzen Rente vom 1. November 2013 bis 28. Februar 2014 und wiederum einer Viertelsrente ab 1. März 2014 in Aussicht. Hiegegen liess A._ Einwände erheben und ein Ärztliches Zeugnis des Dr. med. C._ vom 25. März 2014 einreichen. Am 10. April 2014 wurde ein Assessment-Gespräch durchgeführt. Von be ruflichen Integrationsmassnahmen sah die IV-Stelle unter Hinweis auf eine im Vordergrund stehende Alkoholproblematik ab. Nach Eingang einer weiteren Stellungnahme des RAD vom 23. Mai 2014 verfügte sie am 19. September 2014 entsprechend dem Vorbescheid vom 10. März 2014.
B.
Eine dagegen erhobene Beschwerde von A._ wies das Kantonsgericht Wallis, Sozialversicherungsrechtliche Abteilung, mit Entscheid vom 7. Oktober 2015 ab.
C.
A._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt sinngemäss, es sei unter Aufhebung des angefochtenen Entscheids die Sache zur Neubeurteilung an die IV-Stelle zurückzuweisen. In prozessualer Hinsicht ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
Die IV-Stelle schliesst auf Beschwerdeabweisung, das Bundesamt für Sozialversicherungen verzichtet auf Vernehmlassung.

Erwägungen:
1.
1.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz auf Rüge hin oder von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht, und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; vgl. auch <ref-law>). Es wendet das Recht von Amtes wegen an (<ref-law>).
1.2. Als Tatfragen nur eingeschränkt überprüfbar sind Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit (<ref-ruling> E. 3.2 S. 397 ff.), ebenso die konkrete Beweiswürdigung (Urteil 9C_204/2009 vom 6. Juli 2009 E. 4.1, nicht publ. in: <ref-ruling>, aber in: SVR 2009 IV Nr. 53 S. 164). Dagegen sind die Beachtung des Untersuchungsgrundsatzes und der Beweiswürdigungsregeln nach <ref-law> sowie der Anforderungen an den Beweiswert von Arztberichten (vgl. dazu <ref-ruling> E. 5.1 S. 232) frei überprüfbare Rechtsfragen (SVR 2014 IV Nr. 20 S. 72, 9C_460/2013 E. 1.3).
2.
2.1. Vorinstanz und IV-Stelle stützten sich massgeblich auf Aktenbeurteilungen der RAD-Ärztin Dr. med. D._ vom 3. März und 23. Mai 2014. Darin kam die Ärztin zum Schluss, der Zustand des Beschwerdeführers habe sich mit dem Fortschreiten der Gonarthrose verschlechtert. Nachdem sich der Versicherte eine Knie-Teilprothese hatte implantieren lassen müssen, sei eine volle Arbeitsunfähigkeit zwischen... und 30. November 2013 nachvollziehbar. Unter Hinweis auf einen komplikationslosen postoperativen Verlauf erachtete Dr. med. D._ die Situation ab 1. Dezember 2013 als "wieder im Rahmen der bereits früher festgelegten Limitationen stabilisiert". Die psychiatrischen Probleme seien unverändert und bewirkten nach Einschätzung der behandelnden Ärzte weiterhin eine Arbeitsunfähigkeit von 50 %. Damit sei die Arbeitsunfähigkeit - entsprechend der RAD-Untersuchung vom Herbst 2007 - wiederum auf 40 % zu veranschlagen.
2.2. Der Beschwerdeführer rügt im Wesentlichen, Vorinstanz und IV-Stelle hätten sich zu Unrecht mit einer Aktenbeurteilung des RAD begnügt, obwohl die letzte Untersuchung durch den RAD aus dem Jahr 2007 datierte und sich der Gesundheitszustand gemäss den aktuellen Attesten seiner behandelnden Ärzte wesentlich verschlechtert habe. Aktenwidrig sei die Feststellung der RAD-Ärztin, gegenüber 2007 habe sich der Gesundheitszustand mit Bezug auf die Gonarthrose nach der komplikationslosen Implantation einer Prothese deutlich verbessert.
3.
3.1. Den Akten ist zu entnehmen, dass das Zentrum E._ der IV-Stelle Ende Dezember 2013 namentlich Berichte des Spitals B._ betreffend die 2013 erfolgte Knieoperation und den anschliessenden Verlauf zukommen liess. Am 10. Februar 2014 reichte das Zentrum E._ ein Ärztliches Zeugnis von Hausarzt Dr. med. C._ nach, dem zu entnehmen ist, dass der Versicherte ab 1. Dezember 2013 und bis auf Weiteres zu 60 % arbeitsunfähig sei, entsprechend einem Arbeitspensum von maximal vier Halbtagen in einer leichten Arbeit. Zur Begründung führte Dr. med. C._ insbesondere aus, seit der Implantation der Knieprothese habe sich das chronische lumbospondylogene Syndrom verschlechtert, auch habe sich aktuell eine Spondylarthrose auf dem Boden einer massiven Osteochondrose entwickelt. In der Folge holte die IV-Stelle die bereits erwähnte Aktenbeurteilung durch den RAD (Dr. med. D._) vom 3. März 2014 ein (E. 2.1 hievor).
3.2. Unbestritten wurde der Versicherte nach dem operativen Eingriff von 2013 durch den RAD nicht persönlich untersucht. Dr. med. D._ kam einzig durch Aktenstudium - abweichend von Dr. med. C._ - zum Schluss, im Anschluss an die komplikationslos verlaufene Knieoperation sei der frühere Zustand ab 1. Dezember 2013 wieder erreicht gewesen. Sie begründete ihre Beurteilung damit, dass im Bericht des Dr. med. C._ vom 25. März 2014 bezüglich der Verschlechterung der Rückenproblematik und den aktuellen Zustand klinische Angaben fehlten, der Versicherte anlässlich des Assessment-Gesprächs vom 10. April 2014 keine Rückenbeschwerden mehr geltend gemacht habe und sich in der medizinischen Dokumentation bezüglich der im April 2014 geklagten Hüftschmerzen nichts fände; zudem habe der Versicherte im Winter Schneekanonen bedienen können.
3.3. Mangels eigener Untersuchung handelt es sich bei den Ausführungen der RAD-Ärztin nicht um Stellungnahmen im Sinn von <ref-law>, sondern - lediglich - um Empfehlungen zur weiteren Bearbeitung des Leistungsbegehrens aus medizinischer Sicht (<ref-law> und <ref-law>; Urteil 9C_405/2015 vom 18. Januar 2016 E. 5.1 mit Hinweisen). Solche RAD-Berichte vermögen sich einzig dazu zu äussern, ob der einen oder anderen ärztlichen Ansicht zu folgen oder aber eine zusätzliche Untersuchung vorzunehmen ist. Angesichts der gesundheitlichen Veränderungen und der Differenzen zwischen den Beurteilungen der RAD-Ärztin einerseits und des Dr. med. C._ anderseits hätten es Vorinstanz und IV-Stelle indes nicht bei den RAD-Aktenbeurteilungen vom 3. März und 23. Mai 2014 bewenden lassen dürfen. Unter Berücksichtigung der erheblichen Verschlechterung der Gonarthrose mit nachfolgend indizierter Teilprothesen-Operation und der weiteren von Dr. med. C._ festgehaltenen gesundheitlichen Veränderungen - bei unbestritten gleich gebliebenem psychischen Gesundheitszustand - kann nicht gesagt werden, dass es im Wesentlichen nur um die ärztliche Beurteilung eines an sich feststehenden medizinischen Sachverhalts ging, welche auch in Form einer reinen Aktenbeurteilung erfolgen kann (z.B. Urteile 9C_405/2015 vom 18. Januar 2016 E. 5.1 und 9C_335/2015 E. 3.1 f. mit Hinweisen namentlich auf <ref-ruling> E. 4.4 S. 470). Namentlich kann aus dem Operationserfolg allein nicht unbesehen darauf geschlossen werden, es sei ohne Weiteres der vorherige Zustand wiederhergestellt. Da die vorhandenen medizinischen Akten keine hinreichend zuverlässige Grundlage bieten, um darüber zu befinden, ob die Arbeitsfähigkeit des Versicherten ab 1. Dezember 2013 40 % betrug (wovon Vorinstanz und IV-Stelle ausgehen) oder sich auf 60 % belief (wie dies Dr. med. C._ attestierte), sind die bestehenden Differenzen durch ergänzende gutachterliche Abklärungen zu klären, welche die Beschwerdegegnerin in Nachachtung der ihr obliegenden Untersuchungspflicht in die Wege zu leiten und hernach über den Leistungsanspruch des Versicherten neu zu befinden hat.
4.
Der obsiegende Beschwerdeführer hat Anspruch auf eine Parteientschädigung (<ref-law>) zulasten der Beschwerdegegnerin, welche überdies die Gerichtskosten zu tragen hat (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Kantonsgerichts Wallis, Sozialversicherungsrechtliche Abteilung, vom 7. Oktober 2015 und die Verfügung der Kantonalen IV-Stelle Wallis vom 19. September 2014 werden aufgehoben. Die Sache wird zur neuen Verfügung an die Kantonale IV-Stelle Wallis zurückgewiesen.
2.
Die Gerichtskosten von Fr. 800.- werden der Beschwerdegegnerin auferlegt.
3.
Die Beschwerdegegnerin hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4.
Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Kantonsgericht Wallis zurückgewiesen.
5.
Dieses Urteil wird den Parteien, dem Kantonsgericht Wallis, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 2. Mai 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Die Gerichtsschreiberin: Bollinger Hammerle