Faits:
A. X._, fonctionnaire auprès de la Ville de Genève depuis 1991, a été licencié par le Conseil administratif le 12 septembre 2007, avec effet au 31 décembre suivant.
Le 15 octobre 2007, assisté de Me Y._, il a recouru au Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) contre cette décision. Une procédure portant le numéro A/3871/2007 (cause n° 1) a été ouverte et le dossier a été attribué au juge chargé d'instruire l'affaire.
Le recours ne satisfaisant pas aux exigences minimales de motivation, le juge délégué a imparti à l'intéressé un délai au 31 octobre 2007 pour compléter son recours, sous peine d'irrecevabilité. Sur demande de Me Y._, le délai a été prolongé au 7 novembre 2007.
Le 12 novembre 2007, une écriture intitulée "recours", portant la date du 7 novembre 2007 et signée par MeY._, mais ne comportant aucune référence à une cause existante, est parvenue au Tribunal administratif. Cet acte concluait notamment à l'annulation de la décision du 12 septembre 2007. L'enveloppe contenant le recours portait au dos une mention manuscrite, avec signature, certifiant que le pli avait été déposé à la poste de Carouge le 7 novembre 2007, après la fermeture de 19h45.
Introduite comme un nouveau recours, cette écriture a reçu le numéro A/4338/2007 (cause n° 2) et a été attribuée à un juge différent de celui saisi de la cause n° 1. Les deux procédures ont alors suivi leur cours, parallèlement.
S'étonnant du long délai qui s'était écoulé entre la prise de la décision attaquée et le dépôt du recours du 7 novembre 2007, le juge délégué à la cause n° 2 a demandé à la Ville de Genève de l'informer de la date de notification de sa décision. Cette dernière a répondu avoir notifié sa décision de licenciement le 13 septembre 2007. Une copie de la réponse a été transmise au mandataire de X._ et un délai au 7 décembre 2007 lui a été imparti pour se prononcer sur la recevabilité.
De son côté, le juge délégué à la cause n° 1, qui avait donné deux délais successifs à Me Y._ en dépit desquels aucune écriture ne lui était parvenue, a informé ce dernier que la cause était gardée à juger. L'avocat n'a pas réagi à ce courrier.
Par arrêt du 4 décembre 2007, le Tribunal administratif a jugé irrecevable, pour défaut de motivation suffisante, le recours déposé le 15 octobre 2007 par X._ (cause n° 1). Me Y._, en l'étude duquel l'arrêt a été notifié, n'a pas réagi.
B. Continuant d'instruire l'affaire dont il était saisi et resté sans nouvelle de Me Y._ malgré le délai au 7 décembre 2007 qui lui avait été imparti, le juge délégué à la cause n° 2 a accordé un nouveau délai à ce mandataire pour se prononcer sur la recevabilité de son recours. Me Y._ n'a jamais répondu à ce courrier.
Le 11 janvier 2008, X._ a écrit au juge délégué à la cause n° 2. Il prenait acte de l'absence de réaction de son mandataire aux injonctions du tribunal, mais se trouvait incapable de répondre lui-même.
Donnant suite à ce courrier, le magistrat a convoqué les parties en comparution personnelle le 8 février 2008. Me Y._ ne s'est pas présenté, sans s'être excusé ni avoir indiqué qu'il avait cessé de défendre les intérêts de son client. L'existence de la première procédure a été portée à la connaissance du juge, qui a demandé aux parties de se prononcer sur la recevabilité du recours et sur la portée de l'arrêt rendu par le Tribunal administratif le 4 décembre 2007. X._ a sollicité la révision de cet arrêt, au motif que le premier juge saisi n'avait pas eu connaissance des écritures complémentaires envoyées par son avocat dans le délai qui lui avait été imparti.
Le 18 février 2008, la cause a été suspendue pour laisser le temps à X._ de trouver un nouvel avocat. Le 4 mars 2008, Me François Membrez s'est constitué pour l'intéressé. La reprise de la procédure a été prononcée le 28 avril 2008. Interpellé par le juge délégué au sujet de l'audience du 8 février 2008 à laquelle il n'avait pas participé et informé de l'existence de l'arrêt litigieux, le nouveau mandataire de l'intéressé a confirmé la demande de révision déposée par son client le 22 septembre 2008.
C. Par arrêt du 7 octobre 2008, le Tribunal administratif a déclaré recevable et a admis la demande de révision déposée le 8 février 2008 par X._ contre l'arrêt du 4 décembre 2007, dans la procédure A/4338/2007. Il a annulé l'arrêt litigieux et ordonné la jonction des procédure A/3871/2007 et A/4338/2007. Il a considéré pour l'essentiel que lorsque l'arrêt litigieux a été délibéré par le Tribunal administratif, le juge délégué à la cause n° 1 n'avait pas connaissance des écritures complémentaires de Me Y._, parvenues au tribunal le 12 novembre 2007. La question de savoir si le courrier en question avait été posté le 7 ou le 8 novembre 2007 était sans pertinence, dès lors que le délai fixé par les magistrats n'était qu'un délai d'ordre et que, selon la pratique constante du Tribunal administratif, un complément au recours envoyé un jour après le délai imparti n'était pas, en principe, sanctionné d'irrecevabilité. Si le juge délégué à la cause n° 1 avait eu connaissance de ces écritures, il les aurait admises et le recours du 15 octobre 2007 n'aurait pas été considéré comme irrecevable.
D. Agissant par la voie du recours en matière de droit public et du recours constitutionnel subsidiaire, la Ville de Genève demande au Tribunal fédéral, sous suite de frais, d'annuler l'arrêt du Tribunal administratif du 7 octobre 2008, de déclarer irrecevable la demande de révision de X._ contre l'arrêt du 4 décembre 2007 dans la cause A/3871/2007 et de confirmer ce dernier arrêt. Subsidiairement, elle conclut au renvoi de la cause à la Cour cantonale pour nouvelle décision dans le sens des considérants. La recourante fait tout d'abord valoir que les conditions de l'<ref-law> sont remplies et que son recours est recevable contre l'arrêt attaqué, qui constitue une décision incidente. Elle reproche par ailleurs au Tribunal administratif d'avoir violé son autonomie communale et appliqué de façon arbitraire des dispositions de procédure cantonale. Elle se plaint également de la violation du principe "ne bis in idem" et de son droit d'être entendue.
Le Tribunal administratif a renoncé à formuler des observations sur les recours. Il s'en rapporte à justice quant à leur recevabilité et persiste dans les considérants et le dispositif de son arrêt. X._ conclut, sous suite de frais et dépens, à l'irrecevabilité des recours et, subsidiairement, à son rejet.
Par ordonnance du 15 janvier 2009, le Président de la Ire Cour de droit public a rejeté la demande d'effet suspensif contenue dans le recours.

Considérant en droit:
1. La recourante a formé, en un seul acte (<ref-law>), un recours en matière de droit public et un recours constitutionnel subsidiaire. Le second étant irrecevable en cas de recevabilité du premier (<ref-law>), il convient d'examiner en priorité si la voie du recours en matière de droit public est ouverte.
2. La décision attaquée admet la demande de révision de l'intimé et annule l'arrêt du Tribunal administratif du 4 décembre 2007. Cet arrêt déclarait irrecevable le recours déposé par l'intéressé le 15 octobre 2007 contre son licenciement. Il s'agit donc, au fond, d'un litige relatif à la résiliation des rapports de services d'un fonctionnaire.
2.1 Selon l'art. 83 let. g LTF, en matière de rapports de travail de droit public - lorsque, comme en l'espèce, la question de l'égalité des sexes n'est pas en cause -, le recours en matière de droit public est irrecevable contre des décisions qui concernent une contestation non pécuniaire. Il ressort du dossier que l'intimé ne conclut pas au versement d'une somme d'argent mais conteste son licenciement, qu'il estime abusif. Dès lors que son action, par son incidence directe sur son traitement salarial, a un but économique et dans la mesure où son objet peut être apprécié en argent, il y a lieu de considérer qu'il s'agit d'une contestation de nature pécuniaire (cf. Fabienne Hohl, Procédure civile, Tome II, 2002, p. 77; Jean-François Poudret, Commentaire de la loi fédérale d'organisation judiciaire, vol. II, 1990, p. 196 ss). Le motif d'exclusion de l'art. 83 let. g LTF n'entre ainsi pas en considération. Pour que le recours soit recevable, il faut encore en principe que la valeur litigieuse minimale de 15'000 fr. soit atteinte (<ref-law>). Si les conclusions ne tendent pas au paiement d'une somme d'argent déterminée, le Tribunal fédéral fixe la valeur litigieuse selon son appréciation (<ref-law>). D'après la recourante, l'action de l'intimé en annulation de son licenciement équivaut à une contestation pécuniaire d'un montant supérieur à 15'000 fr., vu qu'elle porte potentiellement sur le salaire de plusieurs mois, voire plusieurs années. Cette estimation n'est pas contestée par l'intimé et il n'y a pas de raison de s'en écarter. La valeur litigieuse déterminante de l'<ref-law> est donc dépassée.
2.2 Le recours est formé par une commune, agissant en tant qu'employeur. Selon l'art. 89 al. 2 let. c LTF, les communes peuvent agir en invoquant la violation de garanties qui leur sont reconnues par la constitution cantonale ou fédérale. La Ville de Genève invoque à ce sujet l'autonomie qui lui est reconnue dans le domaine de la gestion de son personnel. La question de l'autonomie dont elle dispose dans le cas d'espèce n'est toutefois pas déterminante dans la mesure où elle pourrait également agir sur la base de l'<ref-law>; en effet, en tant qu'employeur, obligée de réintégrer un employé après un licenciement abusif, la recourante est touchée de manière analogue à un employeur privé (cf. <ref-ruling> consid. 2.3 p. 207 s.).
2.3 La voie du recours en matière de droit public étant en principe ouverte contre l'arrêt attaqué, sous réserve des conditions de recevabilité posées notamment aux <ref-law>, le recours constitutionnel subsidiaire est irrecevable.
3. 3.1 D'après la loi sur le Tribunal fédéral, le recours en matière de droit public est recevable contre les décisions qui mettent fin à la procédure (<ref-law>) ou contre les décisions partielles (<ref-law>). En revanche, en vertu de l'<ref-law>, les décisions incidentes notifiées séparément qui ne portent pas sur la compétence ou sur une demande de récusation (cf. <ref-law>) ne peuvent faire l'objet d'un recours en matière de droit public que si elles peuvent causer un préjudice irréparable (let. a), ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (let. b). Si le recours n'est pas recevable au regard de ces conditions ou s'il n'a pas été utilisé, la décision incidente peut être attaquée par un recours contre la décision finale dans la mesure où elle influe sur le contenu de celle-ci (<ref-law>).
3.2 L'arrêt attaqué, qui a pour seul but de statuer sur la demande de révision formée par l'intimé contre l'arrêt du Tribunal administratif du 4 décembre 2007, ne met pas un terme à la procédure (cf. arrêt 5P.27/1992 du 27 mai 1993 consid. 1b). Le Tribunal administratif précise en effet que la recevabilité et le fond du recours interjeté par X._ contre la décision de la Ville de Genève du 12 septembre 2007 prononçant son licenciement seront traités dans un arrêt séparé, après que les mesures d'instructions aient été ordonnées. Formellement, il s'agit donc d'une décision incidente, qui ne peut faire l'objet d'un recours en matière de droit public que si les conditions de l'<ref-law> sont réalisées.
4. Un préjudice irréparable au sens de l'<ref-law> est un dommage qui ne peut pas être réparé ultérieurement par un jugement final ou une autre décision favorable au recourant (<ref-ruling> consid. 2.1 p. 190 et les références). La prolongation de la procédure ou un accroissement des frais de celle-ci n'est pas considéré comme un dommage irréparable (<ref-ruling> consid. 2.3.1 p. 632 et les références). Il appartient au recourant d'alléguer et d'établir la possibilité que la décision incidente lui cause un dommage irréparable, à moins que celui-ci ne fasse d'emblée aucun doute (<ref-ruling> op. cit.).
En l'espèce, la recourante n'allègue pas que l'arrêt attaqué lui ferait courir un risque de préjudice irréparable. Au demeurant, on ne voit pas en quoi elle subirait un tel préjudice si le Tribunal administratif entrait en matière sur le recours interjeté par l'intimé contre son licenciement; en effet, le jugement au fond peut tout aussi bien trancher en faveur qu'en défaveur de l'intimé. Partant, le présent recours est irrecevable sous l'angle de l'<ref-law>.
5. Il reste à examiner si la lettre b de l'<ref-law> peut entrer en ligne de compte.
5.1 L'ouverture du recours, prévue pour des motifs d'économie de procédure (<ref-law>), contre une décision incidente constitue une exception, les parties ne subissant aucun préjudice lorsqu'elles n'attaquent pas immédiatement de telles décisions qu'elles peuvent contester en même temps que la décision finale (<ref-law>). Le Tribunal fédéral examine librement le point de savoir si l'admission du recours permettrait d'éviter une procédure d'administration des preuves longue et coûteuse (<ref-ruling> consid. 1.2 p. 412; <ref-ruling> consid. 3.2 p. 292).
5.1.1 La première des deux conditions, cumulatives, requises par l'<ref-law> est réalisée si le Tribunal fédéral peut mettre fin une fois pour toutes à la procédure en jugeant différemment la question tranchée dans la décision préjudicielle ou incidente (cf. <ref-ruling> consid. 4.1 p. 791 s. et les arrêts cités). Cette première condition est manifestement réalisée en l'espèce, puisque si le Tribunal fédéral parvenait à la solution inverse de celle retenue par la Cour cantonale, le recours de l'intimé contre son licenciement serait irrecevable, ce qui mettrait fin définitivement à la procédure.
5.1.2 Quant à la seconde condition, il appartient au recourant d'établir qu'une décision finale immédiate permettrait d'éviter une procédure probatoire longue et coûteuse, si cela n'est pas manifeste; il doit en particulier indiquer de manière détaillée quelles questions de fait sont encore litigieuses, quelles preuves - déjà offertes ou requises - devraient encore être administrées et en quoi celles-ci entraîneraient une procédure probatoire longue et coûteuse (<ref-ruling> consid. 2.4.2 p. 633 et les arrêts cités; <ref-ruling> consid. 3.2 p. 292).
La recourante fait valoir que si la procédure devant le Tribunal administratif devait se poursuivre, celui-ci devrait continuer à instruire le dossier, c'est-à-dire en particulier entendre les parties en comparution personnelle et procéder à l'audition des témoins des deux parties. A ce propos, elle énumère une liste d'une dizaine de témoins dont elle envisagerait de demander la citation. Ceci ne suffit manifestement pas pour admettre la réalisation de la seconde condition requise par l'<ref-law>. En effet, la recourante n'indique pas en quoi l'audition des parties et des témoins prendrait particulièrement beaucoup de temps. Elle ne prétend par ailleurs pas que l'affaire serait très complexe et exigerait des mesures d'instruction coûteuses.
Le présent recours est ainsi également irrecevable au regard de l'<ref-law>.
6. Il résulte de ce qui précède que le recours en matière de droit public et le recours constitutionnel subsidiaire sont irrecevables. L'intimé, qui obtient gain de cause, a droit à des dépens, à la charge de la Ville de Genève (<ref-law>). Il n'est pas perçu de frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public est irrecevable.
2. Le recours constitutionnel subsidiaire est irrecevable.
3. Il n'est pas perçu de frais judiciaires.
4. Une indemnité de 2'000 fr. est allouée à l'intimé à titre de dépens, à la charge de la Ville de Genève.
5. Le présent arrêt est communiqué aux parties et au Tribunal administratif du canton de Genève.
Lausanne, le 23 février 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: La Greffière:
Aemisegger Mabillard