Faits:
A. A.a S._ travaillait en qualité de grutier et exerçait une activité accessoire de nettoyeur. Le 12 avril 1997, il s'est blessé à la cheville droite en jouant au football. Il a subi une fracture-luxation (type Maisonneuve), une fracture partielle de la malléole postérieure et une déchirure du ligament deltoïde, qui ont nécessité une opération, pratiquée par la doctoresse D._, le 18 avril suivant. Depuis lors, il n'a plus été en mesure de reprendre ses anciennes activités professionnelles. La Caisse nationale suisse d'assurance en cas d'accidents (CNA) a pris en charge le cas.
Par décision du 24 décembre 1999, la CNA a alloué une rente, fondée sur une incapacité de gain de 45 %, dès le 1er octobre 1999, ainsi qu'une indemnité pour atteinte à l'intégrité de 5 %. Elle a considéré, sur la base d'une appréciation (du 22 septembre 1998) de son médecin d'arrondissement, le docteur A._, que l'assuré conservait une capacité de travail résiduelle totale dans une activité en position assise ou en alternant la position assise et debout avec des déplacements en terrain plat, sans longues marches, stations debout prolongées ou utilisation d'échelles.
Entre-temps, le 10 décembre 1997, S._ a présenté une demande de prestations de l'assurance-invalidité. Du 23 novembre 1998 au 5 mars 1999, il a suivi un stage d'observation professionnelle, puis a été soumis à une expertise auprès du docteur U._, spécialiste en chirurgie orthopédique, qui a rendu des conclusions similaires à celles du médecin de la CNA (rapport du 15 avril 1999). Sur cette base, l'Office cantonal genevois de l'assurance-invalidité (OCAI) a fixé le taux d'invalidité de l'assuré à 45 % et lui a octroyé un quart de rente avec effet au 1er avril 1998, assorti des rentes complémentaires pour sa famille, ainsi qu'une aide au placement (cf. décision du 14 avril 2000).
A.b Le 3 mars 2000, l'OCAI a accordé à S._, au titre de mesure professionnelle, une formation en qualité d'ouvrier spécialisé dans la fabrication de bâches de stores. Sa rente a été remplacée par des indemnités journalières. Le prénommé a toutefois interrompu cette formation au mois d'août de la même année en raison d'une incapacité de travail de 100 %. L'OCAI a alors requis le docteur U._ d'examiner à nouveau l'assuré (rapport du 31 juillet 2001). Par décision du 5 novembre 2001, l'OCAI a derechef alloué un quart de rente dès le 1er septembre 2000. Le 4 novembre 2002, l'assuré a débuté de sa propre initiative une activité à mi-temps comme magasinier auprès de l'entreprise W._ SA.
A.c Le 30 janvier 2004, S._ a demandé la révision de son droit à la rente, invoquant le fait que son état de santé s'était aggravé et qu'il était en incapacité de travail totale depuis le 3 octobre 2003. Il a produit plusieurs rapports médicaux (en particulier de la doctoresse D._). D'autres documents provenant du dossier de la CNA ont également été versés à l'instruction de sa demande de révision (notamment une expertise du docteur E._). Après avoir requis l'avis du Service médical régional de l'assurance-invalidité, l'OCAI a rejeté cette demande, par décision du 8 décembre 2006.
La CNA, de son côté, à laquelle l'intéressé avait annoncé une rechute, a également refusé d'augmenter la rente LAA qu'elle lui versait (décision du 3 juin 2004, confirmée sur opposition le 14 novembre 2007). Saisi d'un recours, le Tribunal cantonal genevois des assurances sociales l'a rejeté, par jugement du 15 septembre 2008 (cause A/4959/ 2007). Par arrêt de ce jour, la Ière Cour de droit social du Tribunal fédéral a rejeté le recours interjeté par S._ contre ce jugement (cause 8C_880/ 2008).
B. L'assuré a déféré la décision de l'OCAI (du 8 décembre 2006) au Tribunal cantonal genevois des assurances. En cours de procédure, il a indiqué qu'il allait se soumettre à une triple-arthrodèse du pied droit le 2 mai 2008 au Centre Z._.
Après avoir procédé à l'audition de la doctoresse D._ et requis des informations auprès des docteurs J._, médecin traitant, R._ et G._, du Centre Z._, le tribunal a débouté l'assuré (jugement du 5 mai 2008).
C. S._ interjette un recours en matière de droit public contre ce jugement dont il requiert l'annulation. Il conclut à la reconnaissance d'une invalidité de plus de 70 % dès le 4 octobre 2003 et, par conséquent, à l'augmentation de son droit à la rente.
L'OCAI conclut au rejet du recours. 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 (art. 82 ss LTF) peut être formé pour violation du droit selon l'art. 95 sv. LTF. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. Cette disposition lui donne la faculté de rectifier ou compléter d'office l'état de fait de l'arrêt attaqué dans la mesure où des lacunes ou erreurs dans celui-ci lui apparaîtraient d'emblée comme manifestes. Quant au recourant, il ne peut critiquer la constatation de faits importants pour le jugement de la cause que si ceux-ci ont été constatés en violation du droit au sens de l'art. 95 LTF ou de manière manifestement inexacte (art. 97 al. 1 LTF).
2. 2.1 Selon l'art. 17 LPGA, si le taux d'invalidité du bénéficiaire de la rente subit une modification notable, la rente est, d'office ou sur demande, révisée pour l'avenir, à savoir augmentée ou réduite en conséquence, ou encore supprimée. Tout changement important des circonstances propre à influencer le degré d'invalidité, et donc le droit à la rente, peut motiver une révision selon l'art. 17 LPGA. La rente peut être révisée non seulement en cas de modification sensible de l'état de santé, mais aussi lorsque celui-ci est resté en soi le même, mais que ses conséquences sur la capacité de gain ont subi un changement important (ATF 130 V 343 consid. 3.5 p. 349, 113 V 273 consid. 1a p. 275; voir également ATF 112 V 371 consid. 2b p. 372 et 387 consid. 1b p. 390).
2.2 Le point de savoir si un tel changement s'est produit doit être tranché en comparant les faits tels qu'ils se présentaient au moment de la dernière décision entrée en force reposant sur un examen matériel du droit à la rente avec une constatation des faits pertinents, une appréciation des preuves et une comparaison des revenus conformes au droit et les circonstances régnant à l'époque de la décision litigieuse (ATF 133 V 108).
3. 3.1 Les premiers juges ont examiné la situation médicale du recourant prévalant au moment de la décision de rente du 5 novembre 2001, puis son évolution jusqu'à la date de la décision litigieuse. En ce qui concernait l'atteinte au pied droit de l'assuré, ils ont constaté que hormis l'avis isolé de la doctoresse D._, la majorité des médecins consultés s'accordaient à dire qu'une activité assise était encore possible à 100 % (selon les rapports des docteurs E._, L._, R._ et G._, établis respectivement les 13 mars 2006, 16 avril 2007 et 5 décembre 2007). Quant aux dorso-lombalgies dont l'assuré s'était également plaint à l'époque (rapport du docteur J._ du 6 novembre 2000), aucun élément au dossier ne montrait qu'elles s'étaient aggravées entre-temps; ces troubles ne nécessitaient apparemment aucun suivi médical. Les limitations à l'exercice d'une activité lucrative par rapport à celles posées par le docteur U._ étant restées sensiblement les mêmes, il n'y avait donc pas de changement de l'état de santé entraînant une diminution de la capacité de travail résiduelle, singulièrement du degré d'invalidité.
3.2 Pour le recourant, c'est à tort que la juridiction cantonale a nié l'existence d'une aggravation de son état de santé à partir du 4 octobre 2003. Il considère que ce point de vue est arbitraire au vu des explications fournies par les docteurs D._ et J._. Ceux-ci indiquaient clairement que l'état de son pied droit s'était objectivement aggravé de telle manière qu'il n'avait pratiquement plus aucune capacité de travail résiduelle (il ne pouvait rester ni debout ni assis plus de 10 minutes sans ressentir des douleurs). Le caractère défavorable de cette évolution avait d'ailleurs également été reconnue par l'expert mandaté par la CNA, le docteur E._.
4. A juste titre, le recourant ne critique pas le point de départ temporel retenu par les premiers juges pour l'examen d'une éventuelle modification du degré d'invalidité au sens de l'art. 17 LPGA. La décision du 5 novembre 2001 constitue en effet la dernière décision entrée en force par laquelle l'intimée a procédé à un examen matériel de son droit à la rente. Cela étant, le grief d'arbitraire dans l'appréciation des preuves et la constatation des faits soulevé par le recourant n'est pas fondé. Il est établi par les nombreux rapports médicaux au dossier qu'il souffre avant tout d'une déformation de l'arrière-pied droit (due à un pied plat valgus et à une synostose). Il n'est pas non plus contestable que la situation s'est péjorée au fil du temps en ce sens qu'une intervention chirurgicale au pied droit s'est révélée nécessaire et que l'assuré n'est plus en mesure de poursuivre son activité de magasinier, la station debout étant désormais totalement contre-indiquée à son état de santé (cf. rapport du docteur L._ du 16 avril 2007). La juridiction cantonale a toutefois explicitement indiqué les raisons qui l'ont conduite à retenir que cette évolution n'avait pas significativement changé l'exigibilité fixée à l'époque par le docteur U._. Le recourant ne formule par ailleurs aucune critique en ce qui concerne la valeur probante des conclusions des docteurs E._, L._, R._ et G._, sur la base desquelles elle a abouti à cette appréciation. La doctoresse D._ exprime certes des réserves au sujet des réelles possibilité de gain de l'assuré compte tenu d'une aggravation des douleurs (cf. le procès-verbal d'audience du 9 juillet 2007). Mais, comme l'a relevé la Cour de céans dans la procédure parallèle en matière LAA (8C_880/2008), celle-ci n'en remet pas pour autant fondamentalement en cause l'évaluation de la capacité de travail résiduelle effectuée par ses confrères qui, sur le plan objectif, ont confirmé le maintien d'une capacité entière dans une activité en position assise. Il n'est dès lors pas arbitraire ou insoutenable d'admettre que cette évaluation reste dans le cadre de ce qui est raisonnablement exigible de l'assuré en vertu de son obligation de diminuer le dommage (cf. art. 6 LPGA). Il s'ensuit qu'aucun reproche ne peut être fait aux premiers juges d'avoir considéré que l'invalidité de l'assuré ne s'était pas modifiée de manière à lui ouvrir le droit à une rente supérieure à un quart. Le jugement entrepris n'est pas critiquable.
5. Vu l'issue du litige, les frais judiciaires sont mis à la charge du recourant (art. 66 al. 1 LTF), qui ne peut prétendre de dépens (art. 68 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais de justice, arrêtés à 500 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal genevois des assurances sociales et à l'Office fédéral des assurances sociales.
Lucerne, le 14 mai 2009
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Ursprung von Zwehl