Faits:
A. R._ a travaillé en qualité de conducteur de poids lourds, avec livraison de palettes et colis, au service de la société X._ jusqu'au 28 novembre 2003. Il a été licencié avec effet au 30 avril 2004 en raison du fait que son état physique ne lui permettait plus d'assumer les tâches demandées (cf. questionnaire de l'employeur du 10 août 2005). Le 14 juillet 2005, l'intéressé a déposé une demande de prestations tendant à l'octroi d'une rente en raison de maux de dos.
Dans le cadre de l'instruction de la cause, l'Office de l'assurance-invalidité pour le canton de Vaud (ci-après: l'OAI) a recueilli l'avis du docteur T._, médecin traitant de l'assuré depuis le mois d'octobre 2004 (cf. rapport du 19 août 2005) et confié la réalisation d'un examen rhumatologique à son Service médical régional (SMR). Retenant le diagnostic avec répercussion sur la capacité de travail de lombalgies chroniques non déficitaires dans un contexte de protrusion discale des deux derniers disques lombaires (M 54.5), le SMR a estimé que la capacité de travail de l'assuré était nulle dans son activité habituelle de conducteur de poids lourds. En revanche, dans une activité adaptée évitant les attitudes en porte-à-faux du tronc, les mouvements répétés de flexion-extension, le port de charges supérieures à 15 kilos, la position assise prolongée au-delà d'une heure et la position debout prolongée au-delà de 45 minutes, la capacité résiduelle de travail de l'assuré était entière depuis le mois d'octobre 2004 (cf. rapport du 13 décembre 2006).
Par projet de décision du 21 mars 2007, confirmé par décision du 29 novembre suivant, l'OAI a rejeté la demande de prestations de l'assuré, au motif que son degré d'invalidité était insuffisant pour ouvrir droit à une rente ou des mesures professionnelles.
Chargée de défendre les intérêts de l'assuré, l'association Procap a informé l'OAI, le 28 décembre 2007, d'une aggravation de l'état de santé de son mandant. A l'appui de son courrier, elle a produit un rapport du nouveau médecin traitant de l'assuré, du 19 décembre 2007. Dans ce dernier, la doctoresse H._, spécialiste FMH en médecine interne et rhumatologie, indiquait que depuis la mi-novembre 2007, son patient présentait des douleurs à l'épaule droite compatibles avec une tendinopathie, lesquelles prétéritaient une reprise de l'activité professionnelle habituelle. Par lettre du 11 janvier 2008, l'OAI a répondu que le rapport de la doctoresse H._ ne lui permettait pas de modifier la décision du 29 novembre 2007.
B. R._ a déféré cette décision au Tribunal cantonal valaisan des assurances, en concluant principalement à l'octroi d'une rente d'invalidité, subsidiairement au renvoi de la cause à l'OAI pour instruction complémentaire et nouvelle décision, le tout sous suite de frais et dépens.
Par jugement du 8 août 2008, la juridiction cantonale a débouté l'assuré de ses conclusions.
C. R._ interjette un recours en matière de droit public contre ce jugement dont il demande l'annulation, en concluant au versement d'une rente entière d'invalidité. Il requiert également le bénéfice de l'assistance judiciaire.
L'intimé conclut implicitement au rejet du recours, tandis que l'Office fédéral des assurances sociales a renoncé à se déterminer.

Considérant en droit:
1. Le recours en matière de droit public peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>), sans être limité par les arguments du recourant ou par la motivation de l'autorité précédente. Le Tribunal fédéral n'examine en principe que les griefs invoqués, compte tenu de l'exigence de motivation prévue à l'<ref-law>, et ne peut aller au-delà des conclusions des parties (<ref-law>). Il fonde son raisonnement sur les faits retenus par la juridiction de première instance (<ref-law>) sauf s'ils ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). Le recourant qui entend s'écarter des faits constatés doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> sont réalisées sinon un état de fait divergent ne peut être pris en considération. Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
2. Le litige porte sur la question du caractère exigible de la reprise d'une activité lucrative par le recourant. La juridiction cantonale a exposé correctement les règles applicables à la solution du litige, si bien qu'il suffit de renvoyer au jugement attaqué.
3. Les premiers juges ont constaté que le recourant, né le 22 février 1947, était âgé de 56 (recte: 58) ans au moment déterminant de la naissance éventuelle du droit à la rente (octobre 2005). Il lui restait dès lors encore plus de six ans avant l'âge légal de la retraite pour faire valoir sa capacité de travail dans une activité adaptée à ses limitations fonctionnelles. Si son âge pouvait certes réduire ses possibilités de retrouver un emploi, il ne rendait toutefois pas cette perspective illusoire, ce d'autant moins que les secteurs de la production et des services comprenaient un large éventail d'activités simples et répétitives dont un nombre significatif d'entre elles étaient légères et, partant, à la portée du recourant.
4. Le recourant conteste uniquement ses chances de retrouver un emploi sur un marché équilibré du travail, compte tenu notamment de son âge avancé qui le rend non attractif pour un éventuel employeur. Il estime que la juridiction cantonale aurait dû apprécier le caractère exigible de la reprise d'une activité lucrative au moment où la décision litigieuse a été rendue le 29 novembre 2007.
5. La question de savoir quel est le moment déterminant pour procéder à l'évaluation de l'invalidité d'un assuré proche de l'âge de la retraite a récemment été laissée ouverte par le Tribunal fédéral dans un arrêt 9C_949/2008 du 2 juin 2009. En l'espèce, il n'y a pas lieu de trancher cette question. En effet, que l'on retienne le moment de la naissance éventuelle du droit à la rente, auquel il y a lieu de se placer pour procéder à la comparaison des revenus (<ref-ruling> consid. 4.1 et 4.2 p. 223 s.) ou le moment de la décision litigieuse, le recourant, alors âgé de 58 ans, respectivement 60 ans, n'avait pas atteint le seuil à partir duquel la jurisprudence considère généralement qu'il n'existe plus de possibilité réaliste de mise en valeur de la capacité résiduelle de travail sur un marché du travail supposé équilibré (cf. arrêt 9C_1043/2008 du 2 juillet 2009), d'autant moins si l'on considère qu'une pleine capacité de travail dans une activité adaptée lui a été reconnue.
Mal fondé, le recours doit être rejeté.
6. Les frais afférents à la présente procédure seront supportés par le recourant qui succombe (<ref-law>). Il a cependant déposé une demande d'assistance judiciaire visant à la dispense des frais judiciaires. Vu que son recours n'apparaissait pas d'emblée voué à l'échec et qu'il dispose de moyens économiques limités, il en remplit les conditions (<ref-law>). Il est toutefois rendu attentif au fait qu'il devra rembourser la caisse du Tribunal, s'il retrouve ultérieurement une situation financière lui permettant de le faire (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. L'assistance judiciaire est accordée au recourant.
3. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant. Ils sont toutefois supportés provisoirement par la caisse du Tribunal.
4. Le présent arrêt est communiqué aux parties, au Tribunal cantonal des assurances du canton du Valais, à l'Office cantonal AI du Valais et à l'Office fédéral des assurances sociales.
Lucerne, le 18 septembre 2009
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Fretz