Faits:
A. Le 29 mars 1984, le Conseil administratif de la Ville de Genève a nommé A._ en qualité de fonctionnaire, machiniste au Grand-Théâtre. Le 1er novembre 1996, il a été nommé en qualité de "chef-constructeur menuisier".
Le 14 décembre 2007, neuf menuisiers du Grand-Théâtre ont écrit à la présidente de la fondation de cette institution pour lui faire part de dysfonctionnements liés à la personne de A._ et au "sous-chef constructeur" qui lui était subordonné. Il était reproché à A._ d'utiliser massivement les ressources en personnel et en matériel du Grand-Théâtre à des fins privées. Il aurait notamment fait travailler un chef d'équipe et des apprentis pour aménager sa maison en France, à plein temps pendant deux ans, puis plusieurs mois par an. Tous les menuisiers de l'équipe auraient été régulièrement mis à contribution. L'intéressé aurait géré les stocks de matériel en fonction de ses besoins personnels, adopté des comportements injustes, humiliants et dénigrants à l'égard de ses subordonnés et critiqué ses supérieurs. Il aurait également ignoré les demandes de ses employés visant à réduire la pénibilité du travail et à améliorer la sécurité et il aurait passé beaucoup de temps en pause ou dans son bureau à ne rien faire. Enfin, il lui était reproché d'utiliser la camionette du Grand-Théâtre pour son propre usage.
B. Donnant suite à cette dénonciation, le Grand-Théâtre et la Ville de Genève ont déposé une plainte pénale contre A._ le 14 janvier 2008.
Le lendemain, le prénommé a été entendu par X._, maire de la Ville et conseiller administratif en charge du département de la culture. Il a déclaré que l'utilisation de l'atelier du Grand-Théâtre à des fins privées était une pratique généralisée, qui se faisait ouvertement. Il a admis avoir bénéficié de cette pratique, mais pas autant que l'ont décrit les dénonciateurs. X._ a indiqué à A._ que le Conseil administratif de la Ville allait ouvrir une enquête administrative, qui serait suspendue pendant la procédure pénale. Selon le procès-verbal de cet entretien, il lui a également demandé s'il souhaitait démissionner "étant entendu qu'il ne pourra plus travailler à la Ville de Genève".
Des employés du Grand-Théâtre ont été entendus le 18 janvier 2008 par le Grand-Théâtre et la Ville de Genève. Il ressortait de ces auditions que plusieurs employés auraient travaillé pendant plus de dix ans pour A._, durant leurs heures de travail au Grand-Théâtre, pour la fabrication du gros oeuvre et du mobilier de sa maison en France, de son appartement à Avully et de son chalet en Valais.
Par décision du 25 janvier 2008, la Ville de Genève a ouvert une enquête administrative à l'encontre de A._ et a prononcé la suspension de son activité et de son traitement, à compter du 25 janvier 2008 et jusqu'à la clôture de l'enquête. Il lui était reproché un comportement incompatible avec sa fonction, de mauvaises relations de travail, un "irrespect des intérêts de la Ville" et une utilisation sans droit des ressources humaines et matérielles de son service afin d'obtenir des avantages pour lui-même et pour des tiers.
C. Le 6 février 2008, A._ a recouru contre cette décision auprès du Tribunal administratif du canton de Genève. Le 9 juillet 2008, la Ville de Genève l'a licencié avec effet immédiat. A._ a également recouru auprès du Tribunal administratif contre cette décision de licenciement, par écriture du 11 août 2008. L'effet suspensif n'a pas été accordé.
Par arrêt du 26 août 2008, le Tribunal administratif a rejeté le recours formé contre la décision du 25 janvier 2008 prononçant la suspension de A._ sans traitement. Il a considéré en substance que X._ ne devait pas se récuser dans la procédure ayant mené à la décision de suspension, dès lors qu'il ne découlait ni du procès-verbal de la séance du 15 janvier 2008, ni des autres pièces du dossier, que le magistrat en question ait fait preuve de prévention à l'égard de A._. Pour le surplus, la suspension n'apparaissait pas disproportionnée, la faute commise, évaluée sur la seule base des faits reconnus, étant grave.
D. Agissant par la voie du recours en matière de droit public et du recours constitutionnel subsidiaire, A._ demande au Tribunal fédéral d'annuler cet arrêt ainsi que la décision prononçant sa suspension sans traitement et de dire qu'il a droit à son traitement à compter du 23 janvier 2008. Il se plaint d'une violation de la garantie d'impartialité déduite de l'art. 29 al. 1 Cst. Il invoque également une application arbitraire (art. 9 Cst.) de diverses normes de droit communal. Le Tribunal administratif se réfère aux considérants de son arrêt. La Ville de Genève s'est déterminée; elle conclut au rejet du recours, dans la mesure de sa recevabilité.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1 p. 275 et les arrêts cités).
1.1 La voie du recours en matière de droit public selon les <ref-law> est en principe ouverte pour contester les décisions concernant les rapports de travail de droit public. Le recourant ne prend pas de conclusions chiffrées, mais il conclut notamment à l'annulation de la décision de suspension sans traitement et à la constatation de son droit à un traitement à compter du 23 janvier 2008. Son action a dès lors, en tout cas partiellement, un but économique et son objet peut être apprécié en argent, si bien qu'il y a lieu de considérer qu'il s'agit d'une contestation de nature pécuniaire (arrêt 1C_116/2007 du 24 septembre 2007, consid. 2 et les références). Il s'ensuit que le motif d'exclusion de l'art. 83 let. g LTF n'entre pas en considération. Dans la mesure où le salaire réclamé par le recourant concerne la période du 23 janvier au 9 juillet 2008, la valeur litigieuse atteint le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public (<ref-law>). Par conséquent, le recours constitutionnel subsidiaire doit être déclaré irrecevable (<ref-law>).
1.2 La décision litigieuse du 25 janvier 2008 prononce la suspension de l'activité du recourant sans traitement, jusqu'à la clôture de l'enquête administrative. Elle est fondée sur l'art. 35 du statut du personnel de l'administration municipale de la Ville de Genève du 3 juin 1986, qui a la teneur suivante:
1Le directeur ou le chef de service peuvent interdire momentanément et pour deux jours au plus, le travail à ceux dont la conduite ou la tenue risquent d'être une entrave à la bonne marche du service.
2Ils doivent en informer immédiatement le conseiller administratif responsable qui peut prolonger cette interdiction; ce dernier en nantit le Conseil administratif.
3Celui-ci peut confirmer la suspension temporaire de l'activité et ordonner simultanément celle du traitement du fonctionnaire en faute, jusqu'au prononcé de la sanction, conformément aux articles 33 et suivants du présent statut.
La suspension préventive est une mesure de sûreté instituée dans l'intérêt de la bonne marche de l'administration, en vue d'une éventuelle mesure définitive de renvoi pour justes motifs. Il s'agit d'une mesure provisoire destinée à supprimer les dysfonctionnements de l'administration lorsque la situation exige une solution immédiate. Fondée sur une appréciation prima facie des faits, elle ne préjuge pas du sort d'une éventuelle procédure de renvoi pour justes motifs. Même si elle peut être ordonnée avant - ou pendant - le déroulement d'une telle procédure, elle ne possède aucun caractère autonome et ne constitue qu'une étape dans le cadre d'une procédure de renvoi (arrêt 1P.613/1999 du 24 janvier 2000 consid. 2b). Dès lors que cette décision ne met pas fin à la procédure (<ref-law>) et qu'elle ne statue pas sur un objet dont le sort est indépendant de celui qui reste en cause (<ref-law>), elle constitue une décision incidente au sens de l'<ref-law>.
1.3 Conformément à l'<ref-law>, le recours n'est ouvert contre une décision incidente que si celle-ci peut 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). Le recourant ne se prévaut pas de cette dernière condition, qui n'entre pas en considération en l'espèce. Il convient dés lors uniquement d'examiner si la décision litigieuse est susceptible de causer un préjudice irréparable au recourant. Il appartient à ce dernier d'alléguer et d'établir que la décision préjudicielle ou incidente lui cause un tel dommage, à moins que celui-ci ne fasse d'emblée aucun doute (<ref-ruling> consid. 2.3.1 p. 632).
1.4 En l'occurrence, la décision finale a déjà été rendue, le renvoi définitif du recourant ayant été prononcé le 9 juillet 2008 par le Conseil administratif de la Ville de Genève. Il est dès lors douteux que la décision de suspension provisoire faisant l'objet du présent recours ait encore une portée propre. Elle constitue en effet une étape préalable à la décision de renvoi et le sort du recours formé contre celle-ci lui apparaît nécessairement lié. Pour le surplus, la décision de suspension provisoire est fondée sur des critères semblables à ceux qui ont conduit au renvoi définitif du 9 juillet 2008, de sorte que le recourant pouvait faire valoir ses griefs sur le fond dans le cadre de son recours contre la décision finale, ce qu'il a d'ailleurs fait dans son écriture du 11 août 2008. Il en va de même du grief relatif à la récusation du conseiller administratif X._, qui a également pris part à la décision de renvoi définitif.
Dans ces circonstances particulières, l'économie de procédure commande que les griefs formés à l'encontre de la décision incidente et de la décision finale soient examinés ensemble. De plus, la décision incidente pourra le cas échéant être attaquée devant le Tribunal fédéral par un recours contre la décision finale aux conditions de l'<ref-law> et on ne voit pas en quoi le recourant aurait un intérêt digne de protection à ce que ses moyens soient examinés immédiatement. Au demeurant, les effets d'un jugement favorable au recourant dans le cadre de la décision de renvoi définitif devraient s'étendre à la décision de suspension provisoire. Si tel ne devait pas être le cas pour des motifs relevant du droit cantonal, il appartenait au recourant de le démontrer. Quoi qu'il en soit, le préjudice irréparable n'apparaissant pas évident en l'espèce, il incombait au recourant, conformément à la jurisprudence susmentionnée, d'alléguer et d'établir les raisons pour lesquelles la décision incidente lui causerait un tel dommage. Par conséquent, l'existence d'un préjudice irréparable n'ayant pas été établie, la décision incidente litigieuse ne peut pas faire l'objet d'un recours au Tribunal fédéral. La solution est la même qu'il s'agisse d'un recours en matière de droit public ou d'un recours constitutionnel subsidiaire, l'<ref-law> étant applicable aux deux voies de droit.
1.5 Le fait que le recourant soulève un grief relatif à la récusation n'y change rien. En effet, pour déterminer si la décision incidente concerne une demande de récusation au sens de l'<ref-law>, il convient de prendre en compte l'objet de ladite décision et non pas les conclusions du recourant (cf. arrêt 2C_507/2008 du 14 juillet 2008 consid. 2.2). Par ailleurs, les griefs relatifs à la récusation ayant également été soumis au Tribunal administratif dans le cadre du recours contre la décision de renvoi définitif, ils pourront être examinés par le Tribunal fédéral si le litige concernant cette dernière décision lui est valablement soumis. Enfin, la décision sur la demande de récusation n'a pas été notifiée séparément en l'espèce (cf. <ref-law>). Dans ces conditions, il ne se justifie pas d'entrer en matière sur le recours sous l'angle de l'<ref-law>.
2. Il s'ensuit que le recours en matière de droit public et le recours constitutionnel subsidiaire doivent être déclarés irrecevables. Le recourant, qui succombe, doit supporter les frais de la présente procédure (<ref-law>). Il n'est pas alloué de dépens à l'intimée (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public et le recours constitutionnel subsidiaire sont irrecevables.
2. Les frais judiciaires, arrêtés à 1000 fr., sont mis à la charge du recourant.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué au mandataire du recourant, à la Ville de Genève et au Tribunal administratif du canton de Genève.
Lausanne, le 13 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