Sachverhalt:
A. M._ (geboren 1964) arbeitete zuletzt bis 22. Januar 2003 als Magaziner und Verkäufer bei der Firma X._. Am 3. November 2003 meldete er sich unter Hinweis auf eine hochgradige Schwerhörigkeit zum Bezug einer Rente bei der Invalidenversicherung an. Nachdem die IV-Stelle des Kantons Basel-Landschaft verschiedene medizinische Gutachten eingeholt, eine Kosten-gutsprache für eine verbesserte Hörgeräteversorgung erteilt und berufliche Integrationsmassnahmen eingeleitet hatte, beurteilte sie den Versicherten als voll arbeitsfähig. Trotzdem veranlasste sie eine polydisziplinäre Untersuchung durch das Institut Y._, welches seinen Bericht am 14. Juni 2006 vorlegte. Darauf abgestützt wies die IV-Stelle mit Verfügung vom 17. November 2006 das Leistungsgesuch aufgrund eines Invaliditätsgrades von 15% ab. Mit Entscheid vom 11. Juli 2007 hiess das Kantonsgericht Basel-Landschaft die hiegegen erhobene Beschwerde teilweise gut, hob die angefochtene Verfügung auf und wies die Angelegenheit zur weiteren Klärung und zum Erlass einer neuen Verfügung zurück. Es hielt fest, dass auf das Gutachten des Instituts Y._ abgestellt werden könne und eine körperlich leichte bis mittelschwere Tätigkeit aus medizinisch-theoretischer Sicht zu 100% zumutbar sei, sofern der Versicherte für derartige Tätigkeiten keiner näher umschriebenen Formen der Kommunikation bedürfe. Die IV-Stelle habe es allerdings unterlassen, die Verweisungstätigkeiten genauer und unter Berücksichtigung der erheblichen Beeinträchtigungen am Arbeitsplatz zu umschreiben. Aus diesem Grund habe die Verwaltungsbehörde zu prüfen, ob eine zumutbare Verwertbarkeit der Restarbeitsfähigkeit in der vorliegend interessierenden Zeitspanne von Januar 2004 bis Oktober 2008 existent gewesen sei.
Mit Verfügung vom 24. Juli 2008 übernahm die IV-Stelle zwei Cochlea-Implantate mitsamt Nachbehandlung für die Dauer von sechs Monaten. Am 14. Oktober 2008 wurde am rechten, am 17. März 2009 am linken Ohr das Implantat eingesetzt. Nachdem der Versicherte ein integrierendes Arbeitstraining absolviert hatte, liess ihn die IV-Stelle erneut durch das Institut Y._ untersuchen (Gutachten vom 21. März 2011). Aufgrund eines Invaliditätsgrades von 37% verneinte die IV-Stelle am 2. November 2011 den Anspruch auf eine Invalidenrente.
B. Hiegegen erhob der Versicherte Beschwerde beim Kantonsgericht Basel-Landschaft. Dieses hiess die Beschwerde mit Entscheid vom 23. August 2012 teilweise gut. Es hob die Verfügung vom 2. November 2011 auf und stellte fest, dass M._ ab 1. Oktober 2009 Anspruch auf eine Viertels-Invalidenrente habe.
C. M._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und unter teilweiser Aufhebung des angefochtenen Entscheides für die Zeit vom 1. Juni 2006 bis 30. September 2008 die Zusprechung einer ganzen, eventuell auch einer halben Invalidenrente und vom 1. Oktober 2008 bis 30. September 2009 eine ganze Invalidenrente, eventualiter die Rückweisung der Sache zur weiteren Abklärung an die Vorinstanz, beantragen. Ferner ersucht er um Gewährung der unentgeltlichen Prozessführung und Verbeiständung.
Während die IV-Stelle auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.

Erwägungen:
1. Das kantonale Gericht umschreibt die Rechtsgrundlagen zum Anspruch auf eine Invalidenrente (Art. 28 Abs. 2 IVG) und zum Einkommensvergleich (Art. 28 Abs. 1 IVG in Verbindung mit Art. 16 ATSG) zutreffend. Darauf wird verwiesen. Richtig sind auch die übergangsrechtlichen Erwägungen, wonach für die Zeit vom 1. Januar 2008 an die neuen Bestimmungen des IVG und der IVV (5. IV-Revision) anwendbar sind (<ref-ruling> E. 1.2.1 S. 447), die allerdings, soweit hier von Bedeutung, keine inhaltliche Änderung zu den vorher gültigen Bestimmungen darstellen.
2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem die Verletzung von Bundesrecht gerügt werden (Art. 95 lit. a BGG). Eine Beanstandung des Sachverhalts ist nur möglich, wenn die Feststellung offensichtlich unrichtig erfolgte oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht sowie die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). Die vorinstanzlichen Feststellungen zum Gesundheitszustand und zur Arbeitsfähigkeit der versicherten Person sind grundsätzlich Entscheidungen über eine Tatfrage (<ref-ruling> E. 3.2 S. 397 ff.), die das Bundesgericht seiner Urteilsfindung zugrunde zu legen hat (Art. 105 Abs. 1 BGG). Ebenfalls Tatfrage ist die konkrete Beweiswürdigung. Dagegen sind die Beachtung des Untersuchungsgrundsatzes und der Beweiswürdigungsregeln nach Art. 61 lit. c ATSG sowie die Einhaltung des Anspruchs auf rechtliches Gehör Rechtsfragen (<ref-ruling> E. 3.2 und 4 S. 397 ff.), die das Bundesgericht im Rahmen der den Parteien obliegenden Begründungs- bzw. Rügepflicht (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; <ref-ruling> E. 1.4.1 und 1.4.2 S. 254) frei überprüfen kann, wendet doch das Bundesgericht das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (vgl. <ref-ruling> E. 2.5 S. 262).
3. Die materielle Rechtskraft eines gerichtlichen Entscheides erstreckt sich auf das, was Streitgegenstand des Verfahrens gebildet hat und materiell gewürdigt und entschieden worden ist. Inwieweit ein (erster) Rückweisungsentscheid die Verwaltungsbehörde und, im Falle einer erneuten Anfechtung, auch die kantonale Rechtsmittelinstanz bindet, ergibt sich aus dem Urteilsdispositiv (<ref-ruling> E. 4a S. 477) und den erklärenden Erwägungen (Grisel, Traité de droit administratif, S. 882; Guldener, Schweizerisches Zivilprozessrecht, 3. Aufl., S. 247 N. 36 in fine; Gygi, Bundesverwaltungsrechtspflege, S. 323; Kölz, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, S. 242). Folglich sind auch die Motive, auf welche sich das Dispositiv seinem rechtlichen Gehalt nach abstützt, für die Behörde, an welche die Sache zurückgeht, verbindlich (Urteil 9C_350/2011 vom 3. Januar 2012 E. 4.1). Solange jedoch über den Streitgegenstand als solchen nicht formell rechtskräftig entschieden worden ist, verbietet sich grundsätzlich die Annahme, einzelne Elemente der streitigen Sache seien bereits formell und materiell rechtskräftig erledigt (Urteil I 157/00 vom 8. November 2001 E. 1b; ZAK 1986 S. 60 E. 1c mit Hinweisen).
4. Mit Entscheid vom 11. Juni 2007 wurde die IV-Stelle angewiesen, darzulegen, in welchem Umfang beim Beschwerdeführer eine faktische Restarbeitsfähigkeit unter Berücksichtigung der konkreten gesundheitlichen Einschränkungen im interessierenden Zeitraum vorliegend war. Es kann offen bleiben, wie detailliert sich die IV-Stelle im Verfahren zur Ermittlung des Invaliditätsgrades im Vorfeld ihrer ersten Verfügung zu möglichen Verweisungstätigkeiten hätte äussern müssen. Tatsache ist, dass sie vorgängig ihrer zweiten Verfügung vom 2. November 2011 den Auftrag des Kantonsgerichts unerfüllt gelassen und keine nähere Umschreibung der genannten Verweisungs-tätigkeiten vorgenommen hat.
4.1 Streitgegenstand des ersten Verfahrens bildete, entsprechend der angefochtenen Verfügung vom 17. November 2006, der Rentenanspruch. Die bei der Ermittlung des Invaliditätsgrades detailliert zu umschreibenden Verweisungstätigkeiten machen als solche nicht den Streitgegenstand aus, sondern bilden einen Teilfaktor im Rahmen der Festsetzung der streitigen Rente. Da im Entscheid vom 11. Juli 2007 nicht über den Streitgegenstand als solchen entschieden worden ist, erwuchsen die Anweisungen des kantonalen Gerichts an die IV-Stelle nicht in materielle Rechtskraft. Trotzdem ist als verfahrensrechtlicher Grundsatz unbestritten, dass sich Parteien eines Gerichtsverfahrens an den ergangenen Entscheid halten müssen, sofern sie - wie hier der Fall - von seiner Anfechtung abgesehen haben und er infolge dessen in formelle Rechtskraft erwachsen ist. Dies gilt namentlich, wenn eine Amtsstelle im verwaltungsinternen Verfahren als Entscheidbehörde aufgetreten und im nachfolgenden Rechtsmittelverfahren Partei geworden ist (vgl. auch erwähntes Urteil 9C_548/2010 E. 4.1; Urteil 9C_522/2007 vom 17. Juni 2008 E. 3.3.1).
4.2 Die IV-Stelle hatte als Beschwerdegegnerin im gerichtlichen Verfahren, welches zum Entscheid vom 11. Juli 2007 führte, Parteistellung inne, weshalb die Anweisungen im Dispositiv und in den Erwägungen des Entscheides für sie verbindlich waren. Entgegen der gerichtlichen Anordnung hatte die IV-Stelle jedoch darauf verzichtet, weitere Abklärungen bezüglich möglicher Verweisungstätigkeiten für den Versicherten vorzunehmen. Eine Verwaltungsbehörde darf indessen die Anweisungen des Gerichts nur unbeachtet lassen, wenn das Ziel der verlangten Instruktion bereits auf andere Weise erreicht werden kann (in diesem Sinne erwähntes Urteil 9C_522/2010 E. 3.3.1).
In der Zeit zwischen dem ersten Entscheid des Kantonsgerichts und dem Erlass der zweiten Verfügung durch die IV-Stelle haben sich keine weiteren Erkenntnisse in Bezug auf die Verwertbarkeit der Restarbeitsfähigkeit beim Beschwerdeführer vor den Cochlea-Implantaten ergeben. Zusätzliche Abklärungen im Sinne der Erwägungen des Rückweisungsentscheides vom 11. Juli 2007 hätten den Invaliditätsgrad aber beeinflussen und sich damit anspruchserheblich auswirken können. Indem das kantonale Gericht diese Vorgehensweise bestätigt, ohne triftige Gründe anzugeben, warum die früher für erforderlich gehaltenen Abklärungen nicht mehr notwendig sein sollen, verletzt es Bundesrecht (Urteil 9C_350/2011 vom 3. Januar 2011 E. 4.2).
5. Die IV-Stelle hat unter Beachtung der Erwägungen aus dem Entscheid vom 11. Juli 2007 (insbesondere Ziffer 5) abzuklären, welche Art Verweisungstätigkeiten im Zeitraum von Januar 2004 bis Oktober 2008 vom Versicherten hätten ausgeübt werden können. Hierbei muss sie die am Arbeitsplatz existenten Beeinträchtigungen in jener Zeit berücksichtigen und prüfen, ob in der damaligen Ausgangslage überhaupt eine zumutbare Restarbeitsfähigkeit vorgelegen hat. Gestützt auf die erlangten Ergebnisse hat die IV-Stelle nachfolgend den Invaliditätsgrad für die Zeit zwischen Januar 2004 und September 2009 zu bestimmen und, je nach dem Ergebnis, die Rente nachzubezahlen.
Die vorinstanzlich zugesprochene Viertelrente der Invalidenversicherung ab 1. Oktober 2009 wurde von keiner Seite angefochten und steht deshalb dem Beschwerdeführer jedenfalls zu (Art. 107 Abs. 1 BGG).
6. Die IV-Stelle hat als unterliegende Beschwerdegegnerin die Gerichtskosten zu tragen (Art. 66 Abs. 1 BGG) und dem Beschwerdeführer eine Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Das Gesuch um unentgeltliche Rechtspflege ist somit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird in dem Sinne gutgeheissen, dass der Entscheid des Kantonsgerichts Basel-Landschaft vom 23. August 2012, soweit nicht den Invalidenrentenanspruch ab 1. Oktober 2009 betreffend, aufgehoben wird. Die Sache wird an die IV-Stelle des Kantons Basel-Landschaft zurückgewiesen, damit sie, nach erfolgter Abklärung im Sinne der Erwägungen, über den Anspruch auf eine Invalidenrente ab Januar 2004 bis September 2009 neu verfüge.
2. Die Gerichtskosten in der Höhe von Fr. 500.- werden der IV-Stelle des Kantons Basel-Landschaft auferlegt.
3. Die IV-Stelle des Kantons Basel-Landschaft hat dem Beschwerdeführer für das Verfahren vor dem Bundesgericht eine Parteientschädigung von Fr. 2'500.- (einschliesslich Mehrwertsteuer) zu bezahlen.
4. Dieses Urteil wird den Parteien, dem Kantonsgericht Basel-Landschaft, Abteilung Sozialversicherungsrecht, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 30. April 2013
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Der Gerichtsschreiber: Widmer