Sachverhalt: A. C._, geboren 1954, verfügt über eine Ausbildung als Maurer/Baufacharbeiter. Bis zur arbeitgeberseitig erfolgten Kündigung auf Ende Oktober 2006 war er in der Firma R._ AG tätig (letzter Arbeitstag: 2. September 2005). Am 30. August 2006 meldete sich C._ unter Hinweis auf Rückenschmerzen, bestehend seit fünf Jahren, bei der Invalidenversicherung zum Leistungsbezug an (Berufsberatung, Umschulung auf eine neue Tätigkeit, Rente). Die IV-Stelle des Kantons Zürich führte erwerbliche Abklärungen durch und zog die Akten der Krankenversicherung bei, welche in den Jahren 2005 und 2006 Taggeldleistungen erbracht hatte, worunter einen Konsiliarbericht des Dr. med. M._, Spezialarzt FMH für physikalische Medizin, speziell Rheumaerkrankungen, vom 25. Juni 2006. Weiter holte sie Berichte ein des Dr. med. M._ vom 16./19. September 2006 und der Klinik B._, (Dr. med. L._), vom 11./ 25. September 2006. Auf Veranlassung des behandelnden Dr. med. S._, Allgemeine Medizin FMH, (Bericht vom 22./23. Februar 2007) fand am 12. November 2006 bzw. 13./ 14. Dezember 2006 (Basistest) im Spital U._ ein Arbeitsassessement statt. Die Berufsberatung der IV führte am 17. April 2007 mit C._ ein Beratungsgespräch durch, anlässlich dessen er "aufgrund der medizinischen und gesundheitlichen Situation" auf eine Arbeitsvermittlung verzichtete und erklärte, er fühle sich nicht arbeitsfähig, was durch seinen Hausarzt Dr. med. S._ bestätigt werde (Verzichtserklärung vom 18. April 2007). Nach Eingang einer Stellungnahme des Regionalen Ärztlichen Dienstes (RAD; Dr. med. T._) vom 8. März 2007 und eines weiteren Berichtes des Dr. med. S._ vom 5. Juni 2007 erliess die IV-Stelle einen leistungsabweisenden Vorbescheid vom 22. Juni 2007. Daraufhin reichte C._ ein Schreiben des Dr. med. P._, FMH für orthopädische Chirurgie, Spital A._, vom 6. September 2007, zu den Akten. Mit Verfügung vom 12. Oktober 2007 hielt die IV-Stelle an ihrer Leistungsabweisung fest. B. Hiegegen liess C._ Beschwerde erheben. Am 30. November 2007 unterzog er sich einem operativen Eingriff im Spital A._ (transpedunkuläre biomedical Stangen-Spondylodese L3/4 beidseits; Hemi-PLIF L4/5 von rechts mit zwei Stryker Cages, dorsomediale Ostim- und Knochenspananlagerung L3/5 links, Foraminotomie, Neurolyse und Dekompression L4/5 rechts), der komplikationslos verlief (Bericht des Dr. med. P._ vom 17. Dezember 2007). In einem Bericht vom 5. November 2008 führte Dr. med. P._ aus, der Verlauf nach der Operation vom November 2007 sei "zeitgerecht". Im Vordergrund stünden nun supra- und infrafusionelle belastungsbedingte Beschwerden, Trapeziusverspannungen bei (ebenfalls) starken Abnützungserscheinungen im Halsbereich. Derzeit seien konservative Massnahmen vorgesehen. Sollten diese erfolglos sein, wäre eine Zweit- oder sogar Drittoperation der HWS zu diskutieren. Das Arbeitsprofil habe sich nicht geändert. Weiterhin ungeeignet seien Arbeiten mit Heben von Gewichten über 5 kg und längerem Sitzen oder Stehen. Das Sozialversicherungsgericht des Kantons Zürich wies die Beschwerde des C._ mit Entscheid vom 31. März 2009 ab. C. C._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und unter Aufhebung des angefochtenen Entscheides die Zusprechung einer "angemessenen" Invalidenrente, rückwirkend ab 1. September 2006, beantragen. Im Sinne eines Eventualantrages ersucht er um Rückweisung der Sache zur ergänzenden Abklärung und rückwirkenden Zusprache einer angemessenen Invalidenrente an die Beschwerdegegnerin. Gleichzeitig ersucht er um Gewährung der unentgeltlichen Prozessführung und Verbeiständung. Vorinstanz und Bundesamt für Sozialversicherungen verzichten auf eine Stellungnahme. Die IV-Stelle schliesst auf Abweisung der Beschwerde. 