Faits:
A. Le 26 octobre 2008, A._ a été arrêté et placé en détention préventive dans le cadre d'une enquête ouverte contre lui pour vol (<ref-law>) et infractions à l'art. 19a de la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (LStup; RS 812.121) et à l'art. 115 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20).
Il lui est reproché d'avoir volé le portefeuille de B._ le 26 octobre 2008, en s'effondrant sur celui-ci à la sortie d'un bar tout en faisant mine d'être ivre. A._ aurait ensuite pris la fuite, avant d'être rattrapé par un tiers qui a réussi à récupérer les 100 fr. que le prénommé aurait dérobés. Le portefeuille a également été restitué à son propriétaire. Le 29 octobre 2008, B._ a été entendu à titre de renseignements et il a signé à cette occasion un document établi par la police du canton de Genève et intitulé "déclaration-plainte", dans lequel il exposait le déroulement du vol, tout en précisant qu'il n'était pas en mesure de donner un signalement du voleur. Sur la base d'une planche photographique et d'une reconnaissance au moyen d'un miroir sans tain, les témoins C._, D._ et E._ ont identifié A._ comme étant l'auteur du vol en question. Lors de son interpellation, le prénommé était en possession d'un morceau de haschich de 2,4 g et il était sous le coup d'une décision d'interdiction d'entrée en Suisse valablement notifiée. L'intéressé conteste le vol mais reconnaît ces deux dernières infractions. Entendu le 26 octobre 2008 par le juge d'instruction du canton de Genève, A._ a été inculpé de vol ainsi que d'infractions à l'<ref-law> et à l'art. 115 LEtr.
Deux condamnations figurent au casier judiciaire de l'intéressé. Il a été condamné le 15 septembre 2006 à deux mois d'emprisonnement avec sursis pendant deux ans pour vol (<ref-law>), opposition aux actes de l'autorité (<ref-law>) et infraction à l'<ref-law>. Le 8 février 2008, il a été sanctionné d'une peine privative de liberté de 20 jours pour vol au sens de l'<ref-law>.
B. Par ordonnance du 31 octobre 2008, la Chambre d'accusation du canton de Genève a prolongé la détention pour deux mois, sur requête du juge d'instruction. Le 27 novembre 2008, le Procureur général du canton de Genève a requis le Tribunal de police de citer A._ comme prévenu des infractions susmentionnées. Le 1er décembre 2008, A._ a présenté une demande de mise en liberté, que la Chambre d'accusation a rejetée par ordonnance du 3 décembre 2008. En substance, cette autorité a considéré que les charges pesant sur l'intéressé étaient suffisantes et que le maintien en détention préventive était motivé par des risques de fuite et de récidive. Elle estimait également que la proportionnalité était encore respectée, l'inculpé devant être prochainement convoqué devant le Tribunal de police. Cette convocation est intervenue le même jour, pour une audience de jugement prévue le 20 janvier 2009.
C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'ordonnance du 3 décembre 2008 et d'ordonner sa mise en liberté immédiate. Il requiert en outre l'assistance judiciaire. La Chambre d'accusation se réfère à sa décision. Le Procureur général du canton de Genève s'est déterminé; il conclut au rejet du recours. En réponse à ces déterminations, le recourant a présenté des observations complémentaires.

Considérant en droit:
1. Les décisions relatives au maintien en détention préventive sont des décisions en matière pénale au sens de l'<ref-law> (cf. <ref-ruling> consid. 1.1 p. 273; Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 p. 4111). Formé en temps utile (<ref-law>) contre une décision prise en dernière instance cantonale (<ref-law>) et qui touche le recourant dans ses intérêts juridiquement protégés (art. 81 al. 1 let. a et b ch. 1 LTF), le recours est recevable.
2. Une mesure de détention préventive n'est compatible avec la liberté personnelle, garantie par les art. 10 al. 2 Cst. et 5 CEDH, que si elle repose sur une base légale (art. 31 al. 1 et 36 al. 1 Cst.), soit en l'espèce l'<ref-law>/GE (cf. également l'art. 27 Cst./GE). Elle doit en outre correspondre à un intérêt public et respecter le principe de la proportionnalité (art. 36 al. 2 et 3 Cst.; <ref-ruling> consid. 2c p. 270). Pour que tel soit le cas, la privation de liberté doit être justifiée par les besoins de l'instruction, un risque de fuite ou un danger de collusion ou de réitération (cf. art. 34 let. a à c CPP/GE). La gravité de l'infraction ? et l'importance de la peine encourue ? n'est, à elle seule, pas suffisante (<ref-ruling> consid. 3a p. 62; <ref-ruling> consid. 4a). Préalablement à ces conditions, il doit exister à l'égard de l'intéressé des charges suffisantes (art. 5 par. 1 let. c CEDH; <ref-ruling> consid. 3; art. 34 in initio CPP/GE). S'agissant d'une restriction grave à la liberté personnelle, le Tribunal fédéral examine librement ces questions, sous réserve toutefois de l'appréciation des preuves, revue sous l'angle restreint de l'arbitraire (<ref-ruling> consid. 2d p. 271).
3. Dans un premier moyen, le recourant conteste l'existence de charges suffisantes.
3.1 Pour qu'une personne soit placée en détention préventive, il doit exister à son égard des charges suffisantes ou des indices sérieux de culpabilité, c'est-à-dire des raisons plausibles de la soupçonner d'avoir commis une infraction. Il n'appartient cependant pas au juge de la détention de procéder à une pesée complète des éléments à charge et à décharge et d'apprécier la crédibilité des personnes qui mettent en cause le prévenu. Il doit uniquement examiner s'il existe des indices sérieux de culpabilité justifiant une telle mesure. L'intensité des charges propres à motiver un maintien en détention préventive n'est pas la même aux divers stades de l'instruction pénale; si des soupçons, même encore peu précis, peuvent être suffisants dans les premiers temps de l'enquête, la perspective d'une condamnation doit apparaître vraisemblable après l'accomplissement des actes d'instruction envisageables (<ref-ruling> consid. 3c p. 146; Gérard Piquerez, Traité de procédure pénale suisse, 2e éd., 2006, p. 540 et les références).
3.2 A l'appui de son grief, le recourant semble alléguer qu'il n'a pas été inculpé de vol au sens de l'<ref-law>, de sorte qu'il ne pourrait pas être jugé pour cette infraction. Il ressort cependant du dossier que le recourant a été formellement inculpé de vol lors de son audition par le juge d'instruction le 26 octobre 2008. Par ailleurs, le recourant soutient qu'une condamnation pour le vol de portefeuille serait exclue au motif que le lésé n'aurait pas déposé plainte pénale à son encontre. Il omet toutefois de mentionner la "déclaration-plainte" signée le 29 octobre 2008. La question de savoir si ce document vaut effectivement plainte pénale au sens de l'<ref-law> peut demeurer indécise, dès lors que le lésé, qui n'a pas expressément renoncé à porter plainte (<ref-law>), conserve la possibilité de le faire dans le délai de trois mois prévu par l'<ref-law>. Ainsi, même si le recourant devait finalement être reconnu coupable d'un vol d'importance mineure au sens de l'<ref-law> ? infraction poursuivie sur plainte ? une condamnation pour ce motif n'apparaît en l'état pas exclue. A cet égard, les charges apparaissent suffisantes, l'intéressé ayant été formellement identifié par trois témoins présents lors des événements. Il en va de même en ce qui concerne les infractions aux <ref-law> et 115 LEtr, le recourant ayant reconnu les faits. Ce premier grief doit donc être rejeté, étant précisé que les critiques relatives à l'importance de la peine encourue se confondent avec la question de la proportionnalité examinée ci-après.
4. Invoquant le principe de la proportionnalité, le recourant soutient en substance que la durée de la détention est excessive au regard de la peine encourue.
4.1 En vertu des art. 31 al. 3 Cst. et 5 par. 3 CEDH, toute personne qui est mise en détention préventive a le droit d'être jugée dans un délai raisonnable ou d'être libérée pendant la procédure pénale. Une durée excessive de la détention constitue une limitation disproportionnée de ce droit fondamental, qui est notamment violé lorsque la durée de la détention préventive dépasse la durée probable de la peine privative de liberté à laquelle il faut s'attendre. Dans l'examen de la proportionnalité de la durée de la détention, il y a lieu de prendre en compte la gravité des infractions faisant l'objet de l'instruction. Le juge peut maintenir la détention préventive aussi longtemps qu'elle n'est pas très proche de la durée de la peine privative de liberté à laquelle il faut s'attendre concrètement en cas de condamnation (<ref-ruling> consid. 4.1 p. 27; <ref-ruling> consid. 2.2 p. 151; <ref-ruling> consid. 2 et 3 p. 257 ss et les références). Il convient d'accorder une attention particulière à cette limite, car le juge de l'action pénale pourrait être enclin à prendre en considération dans la fixation de la peine la durée de la détention préventive à imputer selon l'<ref-law> (<ref-ruling> consid. 4.1 p. 170 et les arrêts cités).
4.2 En l'occurrence, le recourant est en détention préventive depuis le 26 octobre 2008. Il a donc subi à ce jour plus de deux mois de détention et la durée de la privation de liberté sera proche de trois mois au jour de l'audience de jugement. Selon la "feuille d'envoi" établie le 27 novembre 2008 par le Procureur général, le recourant est renvoyé en jugement pour vol (<ref-law>) et infractions aux <ref-law> et 115 LEtr. Le vol simple est puni d'une peine privative de liberté de cinq ans au plus ou d'une peine pécuniaire. L'infraction à l'<ref-law> est passible de l'amende (ch. 1), voire d'une simple réprimande dans les cas bénins (ch. 2). Quant à l'art. 115 LEtr, il prévoit une peine privative de liberté d'un an au plus ou une peine pécuniaire.
4.3 L'infraction pour laquelle le recourant a été arrêté est un vol de portefeuille. Il ne ressort pas du dossier que l'auteur de ce vol ait fait usage de violence ou de menace, la décision attaquée et la "feuille d'envoi" du Procureur général ne retenant pas un tel élément. De plus, la somme subtilisée se monte à 100 fr. seulement. Même si l'on peut admettre que l'auteur de l'infraction pouvait espérer obtenir davantage, il ne s'agit pas d'un vol important, susceptible de justifier une peine privative de liberté relativement sévère. L'infraction à l'<ref-law> ne saurait aggraver cette peine de manière significative, dès lors que cette infraction est elle-même punie uniquement de l'amende ou d'une réprimande et dans la mesure où elle consiste en la possession de 2,4 g de haschich destinés à la consommation personnelle de l'intéressé. S'agissant de l'infraction à l'art. 115 LEtr, il est reproché au recourant d'avoir séjourné en Suisse sans permis et d'être demeuré dans ce pays malgré une interdiction d'entrée notifiée en 2006. Il convient de relever à cet égard que la présence de l'intéressé en Suisse peut s'expliquer par le fait qu'il est vraisemblablement le père de l'enfant de F._, ressortissante suisse chez qui il vit. De plus, cette infraction apparaît en l'espèce comme secondaire, le recourant ayant été interpellé à au moins quatre reprises entre 2006 et 2008 pour infraction à la législation sur les étrangers, sans que la police ne donne suite à ces arrestations et sans qu'aucune sanction n'ait été prononcée pour ce motif. Ainsi, sans préjuger de la sanction qui sera fixée par le juge du fond, on peut admettre que ce comportement ne saurait conduire au prononcé d'une peine de plusieurs mois de détention. Enfin, il est vrai que le recourant est en situation de récidive, puisqu'il a déjà été condamné pour vol en septembre 2006 et février 2008. Cela étant, selon l'extrait du casier judiciaire, il s'agissait de vols au sens de l'<ref-law>, qui ont donné lieu à des condamnations relativement modestes. Pour le surplus, il ne ressort pas du dossier ni de la décision attaquée que ces infractions étaient graves.
4.4 Dans ces conditions, il y a lieu de constater que la détention préventive du recourant est à ce jour très proche de la durée de la peine privative de liberté à laquelle il faut s'attendre en cas de condamnation. Il y a même lieu de craindre que la détention ne dépasse la peine encourue concrètement si elle devait se poursuivre jusqu'au jour de l'audience de jugement. La durée de la détention préventive est dès lors excessive au sens de la jurisprudence susmentionnée et le maintien en détention du recourant viole le principe de la proportionnalité. Il convient dès lors d'ordonner sa mise en liberté immédiate.
5. Il s'ensuit que le recours doit être admis, sans qu'il soit nécessaire d'examiner les autres griefs soulevés par le recourant. L'ordonnance attaquée doit donc être annulée et la libération provisoire du recourant ordonnée. Il n'y a pas lieu de percevoir des frais judiciaires (<ref-law>). Le recourant, assisté d'un avocat, a droit à des dépens, à la charge de l'Etat de Genève (<ref-law>). Dans ces conditions, sa demande d'assistance judiciaire est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'ordonnance du 3 décembre 2008 de la Chambre d'accusation du canton de Genève est annulée.
2. A._ est mis en liberté provisoire.
3. Il n'est pas perçu de frais judiciaires.
4. Un indemnité de 2000 fr. est allouée à A._ à titre de dépens, à la charge de l'Etat de Genève.
5. Le présent arrêt est communiqué à la mandataire du recourant, au Procureur général et à la Chambre d'accusation du canton de Genève.
Lausanne, le 7 janvier 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener