Sachverhalt:
A. Der 1965 geborene P._ meldete sich am 29. August 2006 unter Hinweis auf ein bestehendes Lumbovertebralsyndrom mit Diskusprotrusion und Diskopathie L1/L2, L3/4 und L4/5 sowie eine depressive Entwicklung zum Leistungsbezug bei der Invalidenversicherung an. Nach beruflichen und medizinischen Abklärungen, u.a. mit Einholung eines psychiatrischen Gutachtens vom 17. November 2007 (Dr. med. W._, Spezialarzt für Psychiatrie und Psychotherapie FMH), sowie nach Durchführung des Vorbescheidverfahrens verneinte die IV-Stelle Basel-Stadt mit Verfügung vom 22. Mai 2008 den Anspruch auf eine Invalidenrente aufgrund eines ermittelten Invaliditätsgrades von 32 %.
B. Die dagegen erhobene Beschwerde des P._ wies das Sozialversicherungsgericht Basel-Stadt mit Entscheid vom 17. Februar 2009 ab.
C. P._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und beantragen, in Aufhebung des angefochtenen Entscheids sei ihm ab 1. Juni 2006 eine Dreiviertelsrente basierend auf einem Invaliditätsgrad von mindestens 60 % zuzusprechen. Eventuell sei die Angelegenheit zur weiteren Sachverhaltsabklärung im Sinne der Darlegungen an die IV-Stelle zurückzuweisen. Ferner wird die unentgeltliche Prozessführung und Verbeiständung beantragt.
Die IV-Stelle schliesst auf Abweisung der Beschwerde. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.

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 auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>; vgl. auch <ref-law>; Ausnahme: Beschwerden gemäss <ref-law> [<ref-law>]). Wie die Sachverhaltsfeststellung ist auch die vorinstanzliche Ermessensbetätigung im Verfahren vor Bundesgericht nur beschränkt überprüfbar. Eine Angemessenheitskontrolle (vgl. <ref-ruling> E. 6 S. 81 [zu Art. 132 lit. a OG]) ist dem Gericht verwehrt; es hat nur zu prüfen, ob die Vorinstanz ihr Ermessen rechtsfehlerhaft ausgeübt, mithin überschritten, unterschritten oder missbraucht hat (vgl. <ref-ruling> E. 3.3 S. 399).
2. Hinsichtlich der für die Beurteilung der Streitigkeit massgebenden gesetzlichen Grundlagen sowie der einschlägigen Rechtsprechung namentlich zur Bedeutung und zum Beweiswert ärztlicher Berichte und Gutachten sowie zur Beweiswürdigung (<ref-ruling> E. 4 S. 99 f. mit Hinweisen [insbesondere auf <ref-ruling> E. 4 S. 261 f.]; <ref-ruling> E. 3 S. 352 ff.; <ref-ruling> E. 1c S. 160 ff., je mit Hinweisen; vgl. auch <ref-ruling> E. 4.1 S. 400) wird auf die zutreffenden Erwägungen im angefochtenen Entscheid verwiesen.
3. 3.1 Das kantonale Gericht hat in Würdigung der medizinischen Aktenlage im Wesentlichen gestützt auf die Berichte des behandelnden Rheumatologen Dr. med. K._ (vom 22. November 2006 und 18. Mai 2007) festgestellt, dass der Beschwerdeführer in der angestammten Tätigkeit als Schaler vollumfänglich arbeitsunfähig ist, dass ihm aber aus rein somatischer Sicht aufgrund des diagnostizierten chronischen rechtsspondylogenen lumbovertebralen Syndroms bei Fehlhaltung/Fehlform und degenerativen Veränderungen der Wirbelsäule mit Diskusprotrusionen eine dem Leiden angepasste, körperlich leichte bis mittelschwere Tätigkeit zu 100 % zumutbar ist. Was die psychische Seite anbelangt, hat die Vorinstanz erkannt, wegen den von Dr. med. W._ im Gutachten vom 24. November 2003 festgehaltenen Verstimmungszuständen bei leichter Depressivität bestehe sodann eine Leistungseinschränkung von 20 %, wobei es hinsichtlich der ebenfalls diagnostizierten somatoformen Schmerzstörung an den rechtsprechungsgemäss geltenden Voraussetzungen (vgl. <ref-ruling> E. 1.2 S. 50 f. mit Hinweisen) fehlen würde, um ausnahmsweise auf mangelnde Überwindbarkeit einer solchen Störung und damit auf deren invalidisierende Wirkung schliessen zu können. Den von der IV-Stelle aufgrund dieser Einschätzung durch Einkommensvergleich (<ref-law> in Verbindung mit <ref-law>) ermittelten Invaliditätsgrad von 32 % hat die Vorinstanz mangels substanziierter Bestreitung sowie fehlender Anhaltspunkte für Rechtsfehler bestätigt.
3.2 Der Beschwerdeführer bringt vor, die vorinstanzliche Feststellung einer 100 %igen Restarbeitsfähigkeit beruhe auf einem offensichtlich unrichtig festgestellten Sachverhalt. Das Gericht habe bezüglich der somatischen Beschwerden in bundesrechtswidriger Weise einzig auf die Angaben zur verbliebenen Arbeitsfähigkeit in den Berichten des Dr. med. K._ abgestellt, obwohl die übrigen involvierten Ärzte lediglich von einer 50 %igen Restarbeitsfähigkeit für leichte, den Rücken nicht belastende Tätigkeiten ausgingen. Wegen der zusätzlichen Einschränkung in psychischer Hinsicht sei sodann mit Blick auf den vorzunehmenden Einkommensvergleich beim Invalideneinkommen nebst einem leidensbedingten Abzug von 20 % weitere 20 % abzuziehen.
3.3 Aus den vom Versicherten angerufenen Einschätzungen der Ärzte am Universitätsspital X._ vom 27. Juni 2006 (Dres. med. M._ und B._) und 11. März 2008 (Dr. med. S._), die den Beschwerdeführer aufgrund der bestehenden chronifizierten lumbovertebralen Beschwerden "zu mindestens 50 % arbeitsfähig" erachteten, zog die Vorinstanz den Schluss, der Gesundheitszustand des Versicherten habe sich (seit 2006) nicht wesentlich verändert und es sei davon auszugehen, dass ihm eine höhere als bloss 50 %ige Arbeitsfähigkeit zugemutet werden könnte. Die knappe ärztliche Formulierung ohne nähere Erläuterung, was unter "zu mindestens 50 % arbeitsfähig" zu verstehen ist, lässt indessen keine zuverlässigen und begründeten Rückschlüsse auf den Grad der Arbeitsunfähigkeit im Sinne der vorinstanzlichen Feststellung zu, zumal das Gericht seinerseits nicht nachvollziehbar dargelegt hat, weshalb diese Aussage ohne Weiteres auch mit der Annahme einer vollständigen Arbeitsfähigkeit vereinbar sein soll. Die Feststellung, bereits im Bericht des Spitals Y._ vom 8. März 2006 sei ein Arbeitsversuch für leichte Tätigkeiten empfohlen worden und die am Universitätsspital erhobenen Befunde würden nicht wesentlich von denjenigen des Dr. med. K._ abweichen, weshalb eine erhebliche Verschlechterung des Gesundheitszustands mit einhergehendem höheren Arbeitsunfähigkeitsgrad nicht anzunehmen sei, liefert diesbezüglich ebenso wenig eine Erklärung wie die Bemerkung des RAD-Arztes Dr. med. V._ vom 11. Juli 2008. Dieser gab an, aus dem Bericht des Orthopäden Dr. med. S._ (vom 11. März 2008) sei zu schliessen, dass er mit der vorbestehenden vollen Arbeitsunfähigkeit nicht einverstanden sei und daher die zumutbare Arbeitsfähigkeit höher einschätze.
Im Weiteren sind auch die Darlegungen zur Restarbeitsfähigkeit des Dr. med. W._ in seinem psychiatrischen Gutachten vom 17. November 2007 insofern nicht widerspruchsfrei, als er einerseits unter dem Titel "Diagnose" der anhaltenden somatoformen Schmerzstörung mit Verstimmungszuständen und der rezidivierenden depressiven Störung (gegenwärtig leichte Episode), Auswirkung auf die Arbeitsfähigkeit beimass und aufgrund der Verstimmungszuständen bei leichter Depressivität von einer um 20 % eingeschränkten Arbeitsfähigkeit ausging (S. 10), andererseits im Abschnitt "Beurteilung und Prognose" zum Schluss gelangte, dass aus psychiatrischer Sicht keine zusätzliche Arbeitsunfähigkeit begründet werden könne und bei einer leidensangepassten Tätigkeit vollständige Arbeitsfähigkeit bestünde; die Arbeitsfähigkeit müsse somatisch begründet werden, eine zusätzliche Verminderung der Arbeitsfähigkeit wegen einer psychiatrischen Erkrankung könne nicht ausgemacht werden.
Angesichts dieser insgesamt nicht eindeutig geklärten, divergierenden Aussagen zur zentralen Frage der verbliebenen Arbeitsfähigkeit lassen die Arztberichte des Dr. med. K._ und sein Attest vom 23. Juni 2008, worin er aufgrund der unterschiedlichen Einschätzung der verbliebenden Arbeitsfähigkeit des Dr. med. S._ eine rheumatologisch-orthopädische gutachterliche Beurteilung für angezeigt hält, sowie die Expertise des Psychiaters Dr. med. W._ hinsichtlich der Restarbeitsfähigkeit keine zuverlässigen Schlüsse zu, welche eine abschliessende Beurteilung des streitigen Rentenanspruchs erlauben würden. Unter diesen Umständen wäre das kantonale Gericht aufgrund des Untersuchungsgrundsatzes (Art. 61lit. c ATSG; E. 1.2 hiervor) gehalten gewesen, weitere Abklärungen zu veranlassen. Die Sache ist daher an die IV-Stelle zurückzuweisen, damit sie ergänzende Abklärungen in Form einer polydisziplinären Begutachtung vornehme und anschliessend über den Rentenanspruch neu entscheide. Damit erübrigen sich hinsichtlich der erwerblichen Auswirkungen des Gesundheitsschadens Weiterungen zu den geltend gemachten Abzügen beim Invalideneinkommen.
4. Die Rückweisung der Sache an die Verwaltung zu erneuter Abklärung (mit noch offenem Ausgang) gilt für die Frage der Auferlegung der Gerichtskosten wie auch der Parteientschädigung als vollständiges Obsiegen im Sinne von Art. 66 Abs. 1 sowie Art. 68 Abs. 1 und 2 BGG, unabhängig davon, ob sie beantragt oder ob das entsprechende Begehren im Haupt- oder im Eventualantrag gestellt wird (<ref-ruling> E. 6.1 S. 235; Urteil 8C_671/2007 vom 13. Juni 2008 E. 4.1). Entsprechend dem Ausgang des Verfahrens sind die Gerichtskosten daher der unterliegenden Beschwerdegegnerin aufzuerlegen. Dem obsiegenden, anwaltlich vertretenen Beschwerdeführer steht eine Parteientschädigung zu. Sein Gesuch um unentgeltliche Rechtspflege ist damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen. Der Entscheid des Sozialversicherungsgerichts Basel-Stadt vom 17. Februar 2009 und die Verfügung der IV-Stelle Basel-Stadt vom 22. Mai 2008 werden aufgehoben. Es wird die Sache an die IV-Stelle Basel-Stadt zurückgewiesen, damit sie über den Anspruch des Beschwerdeführers auf eine Invalidenrente neu verfüge. Im Übrigen wird die Beschwerde abgewiesen.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer 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 Sozialversicherungsgericht Basel-Stadt zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht Basel-Stadt und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 24. November 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Die Gerichtsschreiberin:
Frésard Polla