Sachverhalt: A. A.a Der 1950 geborene D._ war bis September 2002 teilzeitlich als Hilfsschreiner bei der Firma S._ angestellt. Nach krankheitsbedingten Absenzen ab September 2001 meldete er sich am 12. März 2002 (Posteingang) unter Hinweis auf chronische Rückenbeschwerden bei der Invalidenversicherung zum Rentenbezug an. Die Medizinische Abklärungsstelle (MEDAS) erstattete am 5. Mai 2003 im Auftrag der IV-Stelle des Kantons Schwyz ein polydisziplinäres Gutachten. Mit Verfügung vom 12. Dezember 2003 verneinte die IV-Stelle den Anspruch auf eine Invalidenrente (Invaliditätsgrad: 28 %), welche sie im Ergebnis mit Einspracheentscheid vom 3. Oktober 2005 (Invaliditätsgrad: 35 %) bestätigte. Mit Entscheid vom 8. Februar 2006 wies das Verwaltungsgericht des Kantons Schwyz die Beschwerde von D._ ab. Das Bundesgericht hiess mit Urteil vom 4. April 2007 (I 251/06) die dagegen erhobene Beschwerde in dem Sinne gut, dass die Sache zur Einholung einer zusätzlichen fachärztlichen Expertise an die IV-Stelle zurückgewiesen wurde. A.b Am 19. März 2008 erstattete die MEDAS im Auftrag der IV-Stelle ein weiteres Gutachten, in dem nebst somatischen Diagnosen eine leichtgradige depressive Episode mit somatischem Syndrom und eine leicht- bis mittelgradige Merkfähigkeitsstörung im Rahmen eines langjährigen Alkoholüberkonsums diagnostiziert wurde. Im Vorbescheid vom 13. Mai 2008 stellte die IV-Stelle eine halbe Invalidenrente ab 1. Februar 2007 in Aussicht (Invaliditätsgrad: 50 %). Mit Verfügung vom 7. Oktober 2008 bestätigte sie den Vorbescheid. B. Die hiegegen eingereichte Beschwerde wies das Verwaltungsgericht des Kantons Schwyz mit Entscheid vom 26. März 2009 ab. C. Mit Beschwerde lässt D._ die Abänderung des vorinstanzlichen Entscheides dahingehend beantragen, dass ihm bereits ab 1. September 2002, spätestens aber ab dem 1. März 2003, eine Invalidenrente zustehe. Eventualiter sei die Sache zu ergänzenden Abklärungen an die Beschwerdegegnerin zurückzuweisen. Ferner wird um unentgeltliche Rechtspflege ersucht. Während die IV-Stelle auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.