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.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Dabei legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder wenn sie auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>; Ausnahme: Beschwerden gemäss <ref-law> [<ref-law>]).
2. Das kantonale Gericht legt die für die Beurteilung der Leistungsstreitigkeit massgebenden materiellrechtlichen ATSG- und IVG-Bestimmungen (je in der bis Ende 2007 gültig gewesenen Fassung) sowie die hierzu ergangene Rechtsprechung zutreffend dar. Darauf wird verwiesen.
3. Streitig und zu prüfen ist der Anspruch auf eine Invalidenrente.
3.1 Die Vorinstanz erwog, der Beschwerdeführer sei aufgrund degenerativer Veränderungen an der Wirbelsäule in der angestammten Tätigkeit zu mindestens 50 % und in einer behinderungsangepassten leichten wechselbelastenden Tätigkeit uneingeschränkt arbeitsfähig. Auf weitere Abklärungen, insbesondere auch auf eine Evaluation der arbeitsbezogenen funktionellen Leistungsfähigkeit (EFL) sei zu verzichten. Das Valideneinkommen sei auf Fr. 61'458.- zu veranschlagen (im Jahre 2004 erzieltes Einkommen, angepasst an die bis 2006 eingetretenen Verhältnisse), das Invalideneinkommen auf Fr. 59'197.- (basierend auf der vom Bundesamt für Statistik herausgegebenen Lohnstrukturerhebung [LSE] 2006 Tabelle TA 1, Median, Anforderungsniveau 4, angepasst an die wirtschaftlichen Verhältnisse im Jahre 2006 [Die Volkswirtschaft 12/2008 Tabelle B9.2 S. 90]). Der Leidensabzug sei auf maximal 10 % zu begrenzen, so dass der Invaliditätsgrad insgesamt 13,3 % betrage. Selbst der Maximalabzug von 25 % ergäbe keinen rentenbegründenden Invaliditätsgrad.
3.2 Der Beschwerdeführer rügt, die Vorinstanz habe den Sachverhalt offensichtlich unrichtig festgestellt. Die von den mit ihm befassten Ärzten erhobenen Diagnosen stimmten offenkundig nicht überein. Die ärztlichen Beurteilungen der Arbeitsfähigkeit reichten von 100 % (Dr. med. M._) über 50 % (Dr. med. L._, Klinik B._) bis 0 % (Dres. med. S._ und P._), so dass die vorinstanzliche Feststellung einer "leichten Divergenz" offenkundig falsch sei. Den Einschätzungen des Dr. med. P._ könne nicht (e contrario) eine volle Arbeitsfähigkeit in einer angepassten Tätigkeit entnommen werden. Die antizipierte Beweiswürdigung, insbesondere der Verzicht auf eine EFL, sei willkürlich. Offenkundig aktenwidrig und willkürlich sei auch die Ermittlung des Valideneinkommens. Die Vorinstanz habe auf das AHV-pflichtige Einkommen im Jahre 2004 abgestellt, obwohl er bereits damals aus gesundheitlichen Gründen nur ein reduziertes Einkommen erzielt habe; zudem würden die Zuschläge gemäss Landesmantelvertrag (LMV) im Bauhauptgewerbe vernachlässigt. Schliesslich seien in Zusammenhang mit der Ermittlung des Invalideneinkommens Ausmass und Art der weiterhin zumutbaren Tätigkeiten nicht gehörig abgeklärt und willkürlich - in Abweichung von der Beschwerdegegnerin - nicht mehr der leidensbedingte Maximalabzug von 25 % gewährt worden.
4. Eine Beweiswürdigung ist nicht bereits willkürlich, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst, wenn der Entscheid offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht oder auf einem offenkundigen Fehler beruht (<ref-ruling> E. 2b S. 56; vgl. auch <ref-ruling> E. 1.3 S. 4 f.). So verhält es sich hier nicht. Zwar trifft es zu, dass die ärztlichen Einschätzungen sowohl bezüglich der diagnostischen Einordnung der degenerativen Wirbelsäuleveränderungen bzw. der Schwere des mehrfach diagnostizierten lumbospondylogenen Syndroms als auch hinsichtlich der Auswirkungen auf die Arbeitsfähigkeit nicht einheitlich sind. Insbesondere die Beurteilung des Dr. med. M._, welcher die Beschwerden als leichtes lumbospondylogenes Syndrom einordnete und aus rheumatologischer Sicht eine vollständige Arbeitsfähigkeit in der angestammten Tätigkeit als Maurer attestierte, weicht ab von den Einschätzungen der übrigen mit dem Versicherten befassten Ärzte. Deren Beurteilungen stimmen immerhin darin überein, dass die Arbeit als Maurer jedenfalls nicht mehr uneingeschränkt möglich ist (wobei Dr. med. V._ am 7. Oktober 2005 sowie die Ärzte an der Klinik B._ am 25. September 2006 eine eingeschränkte Zumutbarkeit attestierten, während Dr. med. S._ in seinem Bericht vom 23. Februar 2007 sogar von einer Unzumutbarkeit ausging), hingegen einer leichten, wechselbelastenden Tätigkeit (wechselhaftes Sitzen und Stehen, kein Heben über 5 kg) nichts entgegen steht (Berichte der Dres. med. V._ vom 7. Oktober 2005 und des Spitals U._ vom 11. Januar 2007 [wonach sogar mittelschwere Arbeiten zugemutet werden können]; vgl. auch Berichte des Dr. med. S._, welcher zwar am 10. Februar 2006 angab auch in einer angepassten Tätigkeit sei die Arbeitsfähigkeit reduziert, am 23. Februar 2007 [nurmehr] ausführte, die Arbeitsfähigkeit in einer angepassten Tätigkeit sei "schwer zu beurteilen", sowie die Einschätzung des Dr. med. P._ vom 5. November 2008, der festhielt, das Arbeitsprofil habe nicht geändert; weiterhin ungeeignet seien Arbeiten mit Heben von Gewichten über 5 kg sowie mit längerem Sitzen oder Stehen). Soweit das kantonale Gericht in pflichtgemässer Würdigung dieser medizinischen Akten mit nachvollziehbarer Begründung abschliessend feststellte, in einer behinderungsangepassten Arbeit (d.h. ohne Heben von Gewichten über 5 kg sowie ohne längeres Stehen oder Sitzen) sei die Arbeitsfähigkeit nicht eingeschränkt, verletzte es kein Bundesrecht. In der Tat lässt sich, unter Berücksichtigung aller medizinischen Unterlagen, auch der Berichte des operierenden Dr. med. P._, nicht sagen, der Beschwerdeführer sei an der Wirbelsäule in einer Weise beeinträchtigt, dass die Ausübung leichter Arbeiten schlechthin ausgeschlossen wäre.
5. 5.1 Der das Arbeitsassessement durchführende Dr. med. N._ gab in seinem Bericht vom 11. Januar 2007 an, die Basistests erlaubten auf Grund der reduzierten Testauswahl und der fehlenden Belastungsdauer keine Beurteilung des zumutbaren zeitlichen Umfanges, weshalb er die Beurteilung der Zumutbarkeit mittels Begutachtung unter Einbezug einer vollständigen EFL empfehle. Die übrigen mit dem Versicherten befassten Ärzte äusserten sich nicht zu einem solchen Test. Die Vorinstanz begründete den Verzicht auf eine EFL damit, dass hievon keine neuen Erkenntnisse zu erwarten wären, weil der Beschwerdeführer im Rahmen des Arbeitsassessements eine mässige Leistungsbereitschaft, am zweiten Testtag eine deutliche Selbstlimitierung gezeigt habe und überzeugt sei, weiterhin nicht arbeiten zu können, so lange die Beschwerden andauerten. Sie erwog, es fehlten Anhaltspunkte, wonach der Versicherte seine Haltung, eine Arbeitssuche mit Hilfe des RAV komme nicht in Frage, geändert habe.
5.2 Ein EFL-Testverfahren ist nicht in jedem Fall durchzuführen, sondern allenfalls in Betracht zu ziehen, wenn sich die beteiligten Fachärzte ausser Stande sehen, eine zuverlässige Einschätzung des leistungsmässig Machbaren vorzunehmen, und deshalb eine konkrete leistungsorientierte berufliche Abklärung als zweckmässigste Massnahme ausdrücklich empfehlen. Die EFL besteht u.a. aus einem ergonomischen Assessement, in dessen Rahmen durch Arbeitssimulationstests (wie Heben und Tragen, Arbeit über Kopfhöhe oder Leitersteigen) das arbeitsbezogene Leistungsvermögen generell und mit Blick auf die angestammte berufliche Tätigkeit konkret beurteilt wird. Die EFL misst somit die Fähigkeit, manuelle Tätigkeiten zu verrichten, und schätzt den Zeitraum, während dessen die Probanden diese im Verlaufe eines ganzen Tages auszuüben im Stande sind. Das umfassende Testverfahren ermöglicht zudem relevante Aussagen zum Leistungsverhalten und zur Konsistenz der versicherten Person, wobei eine allfällig beobachtete Symptomausweitung und Selbstlimitierung im Rahmen eines chronifizierten Zustandes für die Bewertung der Zumutbarkeit bedeutsam sein kann. Steht ein Schmerzsyndrom im Vordergrund, wird eine objektive Evaluation des funktionellen Leistungsvermögens zwar schwieriger, weil die Anstrengung oft durch eine Selbstlimitierung geprägt ist; auch in solchen Fällen erlaubt die EFL indes eine Quantifizierung der Leistungen, welche die Probanden einverstanden sind zu erbringen (Urteil 8C_547/2008 vom 16. Januar 2009 E. 4.2.1 mit Hinweisen, in: SVR 2009 IV Nr. 26 S. 73). Eine Selbstlimitierung allein spricht somit nicht grundsätzlich gegen eine EFL, solange die versicherte Person bereit und einverstanden ist, sich einem entsprechenden Testverfahren zu unterziehen und Leistungen zu erbringen.
5.3 Abgesehen davon, dass im Unterschied zu dem in SVR 2009 IV Nr. 26 S. 73 beurteilten Fall (E. 5.1 hievor) hier nicht mehrere involvierte Ärzte eine EFL ausdrücklich befürwortet hatten, sondern nur (aber immerhin) der das Arbeitsassessement durchführende Dr. med. N._ eine solche anregte, ist in Würdigung der vom Versicherten mehrfach betonten Überzeugung, nicht arbeiten zu können und seiner klaren Ablehnung einer Arbeitsvermittlung (Arbeitsassessementbericht vom 11. Januar 2007; vgl. auch Verlaufsprotokoll Arbeitsvermittlung vom 17. April 2007 sowie Verzicht auf Arbeitsvermittlung vom 18. April 2007) in der Tat nicht davon auszugehen, dass eine EFL zusätzliche neue Erkenntnisse bringen würde. Denn die Testergebnisse sind bezüglich zumutbarer Belastbarkeit nur bei guter Leistungsbereitschaft zuverlässig. Wo eine solche fehlt, kann die Zumutbarkeit einer Arbeitsleistung nicht anders beurteilt werden als ausgehend vom medizinisch-theoretischen Zustand, welcher "bei normaler Leistungsbereitschaft und mittels der bisherigen zumutbaren Behandlungen mit hoher Wahrscheinlichkeit mindestens erreichbar gewesen wäre" (Oliveri/Kopp/ Stutz/Klipstein/Zollikofer, Grundsätze der ärztlichen Beurteilung der Zumutbarkeit und Arbeitsfähigkeit, Teil 2, in: Schweiz. Med. Forum 6/2006 S. 450). Der in antzipierter Beweiswürdigung erfolgte Verzicht des kantonalen Gerichts auf eine solche Evaluation verstösst damit im Ergebnis nicht gegen Bundesrecht.
6. Hinsichtlich der vorinstanzlich zu Recht nach der allgemeinen Methode des Einkommensvergleich vorgenommenen Invaliditätsbemessung rügt der Beschwerdeführer eine zu niedrige Festsetzung des ohne Gesundheitsschaden hypothetisch erzielbaren Einkommens (Valideneinkommen) sowie den im angefochtenen Entscheid auf 10 % festgesetzten behinderungsbedingten Abzug vom Tabellenlohn beim Invalideneinkommen. Wie es sich damit verhält, braucht indes nicht weiter geprüft zu werden. Selbst wenn der Invaliditätsberechnung das vom Beschwerdeführer geltend gemachte Valideneinkommen von Fr. 68'263.- im Jahre 2006 zu Grunde gelegt würde (welches sich auch durch Aufrechnung des im Jahre 2003 erzielten Einkommens von Fr. 66'549.- an die bis 2006 eingetretene Lohnentwicklung [im Baugewerbe] von + 0,4 % [2004], + 1,1 % [2005] und +1,1 % [2006] in etwa bestätigt; Die Volkswirtschaft 12/2007 Tabelle B10.2 S. 99) und von dem vom Versicherten zu Recht nicht bestrittenen, vorinstanzlich gestützt auf die LSE 2006 korrekt auf Fr. 59'197.- ermittelten Invalideneinkommen der Maximalabzug von 25 % in Abzug gebracht würde, resultierte kein rentenbegründender Invaliditätsgrad (Valideneinkommen: Fr. 68'263.-; Invalideneinkommen: Fr. 44'397.75.-; Invaliditätsgrad: 35 %).
7. Dem Gesuch um unentgeltliche Rechtspflege, einschliesslich der unentgeltlichen Verbeiständung, kann entsprochen werden, da die Bedürftigkeit ausgewiesen ist, die Beschwerde nicht als aussichtslos bezeichnet werden kann und die anwaltliche Vertretung geboten war (Art. 64 Abs. 1 und 2 BGG). Der Beschwerdeführer wird aber darauf hingewiesen, dass er der Gerichtskasse Ersatz zu leisten hat, wenn er später dazu in der Lage ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Rechtsanwalt Dr. André Largier, Zürich, wird als unentgeltlicher Anwalt des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'500.- ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 25. November 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle