Faits:
A. Par décision du 3 octobre 2008, l'office cantonal de l'assurance-invalidité de Genève (ci-après: l'OCAI) a alloué à C._ une rente d'invalidité de 853 fr. par mois à partir du 1er novembre 2008, fondée sur un taux d'invalidité de 60%.
Par lettre du 10 novembre 2008, adressée par fax à l'OCAI, l'assuré a contesté la décision du 3 octobre 2008. Par courrier du 11 novembre 2008, l'OCAI a transmis cette correspondance au Tribunal cantonal des assurances sociales de Genève comme objet de sa compétence.
B. Ainsi saisi, le tribunal des assurances a constaté que l'écriture du recourant n'était pas signée en original et lui a imparti un délai au 24 novembre 2008 pour qu'il retourne l'acte de recours dûment signé.
Par jugement du 10 décembre 2008, le tribunal des assurances a déclaré irrecevable le recours de l'assuré, au motif que ce dernier n'avait pas retourné l'acte de recours signé en original dans le délai fixé.
C. C._ interjette un recours en matière de droit public contre ce jugement dont il requiert implicitement l'annulation. Dans son recours, il prétend avoir envoyé à l'OCAI l'acte de recours cantonal signé en original le 20 novembre 2008. En outre, il demande à être dispensé de l'avance de frais.
Invité à se déterminer sur le recours, l'OCAI conclut à son rejet, tandis que l'Office fédéral des assurances sociales ne s'est pas prononcé.
Interpellé par le Tribunal fédéral, l'OCAI a produit l'acte de recours de C._ contre sa décision du 3 octobre 2008 signé en original ainsi que l'enveloppe dans laquelle il avait été envoyé, munie du sceau de la poste attestant de sa remise à l'office postal le 20 novembre 2008.

Considérant en droit:
1. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est pas lié par les motifs que les parties invoquent, de sorte qu'il peut admettre le recours pour d'autres raisons que celles avancées par le recourant ou, au contraire, confirmer la décision attaquée pour d'autres motifs que ceux retenus par l'autorité précédente (<ref-ruling> consid. 1.4.1 et 1.4.2 p. 254; arrêt 9C_562/2008 du 3 novembre 2008, consid. 1). Le Tribunal statue sur la base des faits établis par la juridiction de première instance qui le lient (<ref-law>), sauf s'ils l'ont été de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (art. 105 al. 2 en relation avec l'<ref-law>).
2. 2.1 Aux termes de l'<ref-law>, tous les organes de mise en oeuvre des assurances sociales ont l'obligation d'accepter les demandes, requêtes ou autres documents qui leur parviennent par erreur. Ils en enregistrent la date de réception et les transmettent à l'organe compétent. La seule exception à cette obligation est donnée lorsque le fait de s'adresser à une autorité incompétente a été consciemment voulu par l'expéditeur (KIESER, ATSG-Kommentar, 2009, n° 13 ad <ref-law>). Selon l'<ref-law> en corrélation avec l'<ref-law>, lorsqu'une partie s'adresse en temps utile à un assureur incompétent, le délai est réputé observé. Ces dispositions ne sont que l'expression, en droit des assurances sociales, d'un principe général du droit administratif, reconnu par la doctrine, et consacré à maintes reprises par la jurisprudence (<ref-ruling> consid. 1; VSI 1995 p. 199 consid. 3b et les références; arrêt H 363/99 du 25 janvier 2000 et les références; arrêt 2C_603/2008 du 11 février 2009, consid. 3; arrêt 9C_867/2008 du 6 avril 2009, consid. 7).
2.2 Dans le cas particulier, l'OCAI ayant été saisi d'une écriture du recourant le 20 novembre 2008 (cf. timbre postal), il aurait dû la transmettre au tribunal des assurances du canton de Genève, ce d'autant plus qu'il avait déjà transmis à la juridiction cantonale, dix jours plus tôt, une correspondance du recourant ayant la même teneur. Dans la mesure où le mémoire signé en original avait le même contenu que le premier mémoire télécopié du 10 novembre 2008, il ne fait aucun doute que le recourant n'avait d'autre intention, avec sa correspondance du 20 novembre 2008, que de parfaire son recours du 10 novembre 2008, conformément à l'injonction du tribunal des assurances. N'ayant pas eu connaissance de l'écriture du recourant du 20 novembre 2008 en temps utile en raison de la violation par l'OCAI de son obligation de transmission, la juridiction cantonale a malgré tout établi les faits d'une façon manifestement inexacte. Par conséquent, il convient d'annuler le jugement entrepris et de renvoyer la cause à l'instance inférieure pour qu'elle rende une nouvelle décision, compte tenu de l'écriture du recourant du 20 novembre 2008.
Le recours en matière de droit public se révèle ainsi bien fondé.
3. Vu l'issue du litige, les frais judiciaires doivent être mis à la charge de l'intimé, qui succombe (<ref-law>). Dans la mesure où il n'est pas représenté par un mandataire professionnel, le recourant, qui obtient gain de cause, n'a pas droit à des dépens (art. 68 al. 1 et 2 LTF; cf. <ref-ruling> consid. 4 p. 446). Sa requête d'assistance judiciaire partielle, portant sur la dispense des frais judiciaires, est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et la décision du Tribunal cantonal des assurances sociales de la République et canton de Genève du 10 décembre 2008 est annulée. La cause est renvoyée à la juridiction cantonale pour nouvelle décision conformément aux considérants.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimé.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal des assurances sociales de la République et canton de Genève et à l'Office fédéral des assurances sociales.
Lucerne, le 11 mai 2009
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Fretz