Faits:
A. A.a P._, né en 1964, a été engagé par X._, Ville de Genève, dès le 1er juillet 2004, au poste de collaborateur technique au Service Y._. Il était affecté à l'unité Z._. Son traitement annuel de base s'élevait à 90'343 fr., ce qui correspondait à la classe 12 annuité 6 de l'échelle des traitements. Au terme d'une période d'essai de trois ans, X._ a confirmé sa nomination, dès le 1er juillet 2007, pour une durée indéterminée. A partir de la même date, sa fonction a été classée en 13ème catégorie de l'échelle des traitements.
A partir du mois de mars 2005, P._ a assuré la gestion de la section V._ et assisté son supérieur hiérarchique dans la direction et la coordination du secteur Z._. Il a été amené à remplacer son supérieur hiérarchique en février et en mars 2006 et durant la période du mois de février 2008 au mois de mars 2009. A ce titre, il a perçu une indemnité mensuelle de remplacement (415 fr. 60 pour les mois de février et mars 2006, 425 fr. 30 de février à décembre 2008 et 428 fr. 20 de janvier à mars 2009).
A partir du mois de mars 2005 également, il a demandé avec l'appui de son supérieur hiérarchique une réévaluation de sa fonction, mais sans succès. Au mois d'août 2008, il a été soumis à un «assessment». Le 3 août 2009, il s'est porté candidat au poste de coordinateur V._. Sa candidature n'a pas été retenue. Il a donné sa démission le 30 novembre 2009 avec effet au 31 décembre 2009. La Ville lui a délivré un certificat de travail daté du 17 mars 2010 et dont le troisième paragraphe était ainsi libellé:
«Au cours de l'année 2005, Monsieur P._ a dû également assister son responsable dans la direction et la coordination du secteur ainsi que le remplacer selon les besoins et effectuer toutes tâches en relation avec la fonction.»
A.b Le 13 janvier 2010, P._, représenté par le Syndicat interprofessionnel des travailleuses et travailleurs (SIT) s'est plaint de ce que sa classification salariale n'avait pas évolué en rapport avec la fonction réellement occupée. Le manque à gagner s'élevait à 18'360 fr., sans compter la perte sur le capital de prévoyance. Le 17 février 2010, X._ a donné une fin de non recevoir à cette requête, en considérant que l'intéressé n'avait été victime d'aucune inégalité de traitement et que, de surcroît, il n'existait aucun droit à une promotion. Le 22 mars 2010, P._, représenté cette fois par un avocat, a réitéré sa demande. Il a également demandé à la Ville de modifier son certificat de travail afin qu'il reflète mieux l'ensemble des attributions et responsabilités qu'il avait exercées en qualité d'adjoint au coordinateur Z._ et qu'il mentionne également qu'il avait exercé ad intérim la fonction de coordinateur Z._. Il a demandé à la Ville de rendre une décision formelle au cas où ses prétentions devaient être rejetées. Le 14 avril 2010, la Ville a répondu qu'elle estimait avoir respecté les dispositions réglementaires en la matière et que, de ce fait, l'intéressé n'avait subi aucun préjudice. P._ a alors demandé à la Ville de rendre une décision formelle. Par lettre du 5 mai 2010, X._ a indiqué qu'il maintenait sa position et qu'il n'avait pas à rendre une décision, car aucune voie de recours n'était ouverte au Tribunal administratif pour obtenir une promotion.
B. Par écriture du 7 juin 2010, P._ a saisi le Tribunal administratif du canton de Genève (depuis le 1er janvier 2011: la Chambre administrative de la Cour de justice) d'un recours en prenant les conclusions principales suivantes:
«Condamner la Ville de Genève à payer à Monsieur P._ la différence entre le salaire qui lui a été versé et le salaire qui aurait dû lui être versé compte tenu des tâches effectuées, soit un traitement en classe 12-14 au moins dès le mois de mars 2005 et un traitement en classe 19 durant les mois de février et mars 2006 et des mois de février 2008 à mars 2009, sous déduction des indemnités de remplacement versées, avec intérêts à 5 % dès le 31 décembre 2009.
Condamner la Ville de Genève à remettre à Monsieur P._ un nouveau certificat de travail dans le sens des considérants».
Par arrêt du 1er février 2011, la Chambre administrative de la Cour de justice a partiellement admis le recours selon le dispositif suivant:
«Condamne la Ville de Genève à verser au recourant:
- du 1er mars au 31 décembre 2005 un traitement correspondant à la classe 13 annuité 0;
- du 1er janvier au 31 décembre 2006 un traitement correspondant à la classe 13 annuité 1;
- du 1er janvier au 30 juin 2007 un traitement correspondant à la classe 13 annuité 2;
- du 1er juillet au 31 décembre 2007 un traitement correspondant à la classe 13 annuité 7;
- du 1er au 31 janvier 2008 un traitement correspondant à la classe 13 annuité 8;
- du 1er février au 31 décembre 2008 un traitement correspondant à la classe 19 annuité 0;
- du 1er janvier au 31 mars 2009 un traitement correspondant à la classe 19 annuité 1;
le tout avec intérêts à 5 % dès le 13 janvier 2010, sous déduction du salaire et des indemnités de remplacement perçus durant ces périodes.»
Au considérant 20 de son arrêt, la chambre administrative a invité la Ville à établir un nouveau certificat de travail «conforme à la proposition faite par M. P._ lors de l'audience de comparution personnelle».
C. C.a Par écriture du 14 mars 2011, P._ a interjeté un recours en matière de droit public et un recours constitutionnel subsidiaire dans lequel il a conclu à l'annulation de l'arrêt attaqué et demandé au Tribunal fédéral de condamner la Ville de Genève à lui verser la différence entre le salaire qui lui avait été payé et le salaire qui aurait dû lui être versé compte tenu des tâches effectuées, soit un traitement en classe 12-14 au moins dès le mois de mars 2005 et un traitement en classe 19 durant les mois de février et mars 2006 et des mois de février 2008 à mars 2009, sous déduction des indemnités de remplacement perçues, avec intérêts à 5 % dès le 31 décembre 2009. Il a également conclu à ce que la Ville lui remette un nouveau certificat de travail conformément à sa proposition faite lors de la comparution personnelle (cause 8C_220/2011).
Le recourant fait valoir que le jugement attaqué contient une contradiction interne. En réalité il ne lui donnerait pas gain de cause, contrairement à ce que voulaient les premiers juges, car ceux-ci ont omis de tenir compte des annuités dont il bénéficiait au moment de son engagement. Le recourant se plaint par ailleurs d'un déni de justice au motif que la condamnation de la Ville à lui remettre un certificat de travail ne figure pas dans le dispositif du jugement attaqué.
C.b Par mémoire du 14 mars 2011, la Ville de Genève a exercé un recours constitutionnel subsidiaire contre l'arrêt du 1er février 2011, dont elle a demandé l'annulation (cause 8D_1/2011).
C.c Parallèlement à ses deux recours, P._ a déposé devant la chambre administrative une demande d'interprétation et de rectification de son arrêt du 1er février 2011. Il lui a demandé d'interpréter son arrêt en ce qui concerne ses prétentions salariales et de le rectifier en ce qui concerne son certificat de travail en complétant son dispositif comme suit: «Condamne la Ville de Genève à remettre à Monsieur P._ un nouveau certificat de travail conforme à la modification proposée lors de l'audience de comparution personnelle des parties du 15 octobre 2010 ».
C.d Par ordonnance du 11 mai 2011, le juge instructeur a joint les causes 8C_220/2011 et 8D_1/2011 et a ordonné la suspension de la procédure jusqu'à droit jugé par la chambre administrative sur la demande d'interprétation et de rectification présentée par P._.
C.e Par arrêt du 21 juin 2011, la chambre administrative a rejeté la demande de rectification, l'absence de toute mention relative au certificat de travail dans le dispositif de son arrêt précédent n'étant pas le résultat d'une erreur de rédaction. Elle a cependant traité la demande de rectification comme une demande d'interprétation, qu'elle a admise en ce sens qu'il doit être ajouté au dispositif de l'arrêt du 1er février 2011 la mention suivante:
«Ordonne à la Ville de Genève de compléter le certificat de travail de Monsieur P._ du 17 mars 2010 en précisant, au troisième paragraphe, que dès l'année 2005, Monsieur P._ a été amené à assurer la gestion de la section V._ et a également dû assister son responsable dans la direction et la coordination du secteur Z._ comprenant la section A._, la section Y._ ainsi que la formation Z._. Par ailleurs, Monsieur P._ a été amené à remplacer son responsable durant une période totale de 17 mois et à effectuer toutes les tâches en relation avec la fonction».
Pour le reste, la juridiction cantonale a jugé que la voie de l'interprétation n'était pas ouverte pour obtenir un nouveau calcul des prétentions salariales visées par le dispositif de l'arrêt du 1er février 2011.
C.f La Ville de Genève a formé un recours constitutionnel subsidiaire contre ce deuxième jugement dont elle a, également, demandé l'annulation (cause 8D_2/2011).
C.g Par une nouvelle ordonnance, du 5 décembre 2011, le juge instructeur a mis fin à la suspension de la procédure ordonnée le 11 mai 2011, a joint la cause 8D_2/2011 aux causes 8C_220/2011 et 8D_1/2011. Il a par ailleurs accordé l'effet suspensif aux recours formés par la Ville de Genève.
C.h P._ s'est déterminé sur les recours de la Ville, tandis que celle-ci s'est déterminée sur l'écriture de son adverse partie.
Considérant en droit:
I. Procédure (recevabilité)
1. 1.1 L'objet du litige est l'arrêt du 1er février 2011 déféré au Tribunal fédéral, tel que rectifié par l'arrêt du 21 juin 2011. Il s'agit d'une décision en matière de rapports de travail de droit public portant sur des prestations pécuniaires (voir en ce qui concerne le certificat de travail: ATF 116 II 379 consid. 2b p. 380; arrêt 8C_151/2010 du 31 août 2010 consid. 2.2, in JdT 2011 II 208). La clause d'exclusion de l'art. 83 let. g LTF n'entre donc pas en considération.
1.2 En matière pécuniaire, le recours n'est en principe recevable que si la valeur litigieuse atteint 15'000 fr. (art. 85 al. 1 let. b LTF). Contrairement à ce que prescrit l'art. 112 al. 1 let. d LTF, la décision attaquée n'indique pas de valeur litigieuse. En cas de recours contre une décision finale, cette valeur est déterminée par les conclusions restées litigieuses devant l'autorité précédente (art. 51 al. 1 let. a LTF). P._ soutient qu'il aurait dû percevoir, en plus de son salaire et des indemnités de remplacement, une somme totale de plus de 20'000 fr. pour toute la durée de son activité au service de la Ville. Celle-ci est d'avis que la valeur litigieuse fondée sur les prétentions salariales de l'intéressé s'élève à 7'065 fr. au plus. Faute d'indications suffisantes au dossier, le Tribunal fédéral n'est pas à même de contrôler précisément si le seuil requis de 15'000 fr. est atteint. On peut toutefois admettre, compte tenu des indications fournies par P._ dans la première écriture qu'il a adressée à la Ville que ses prétentions salariales, ajoutées à la valeur que peut représenter pour lui une modification de son certificat de travail sur des points importants (pour des exemples et sur les critères à prendre en considération, voir l'arrêt 8C_151/2010, précité, consid. 2.5 à 2.8), que le seuil requis de 15'000 fr. est atteint et même dépassé. La voie du recours en matière de droit public est donc ouverte dans ce cas. Le recours constitutionnel subsidiaire formé par P._ est donc irrecevable (art. 113 LTF).
2. 2.1 La Ville a formé deux recours constitutionnels subsidiaires, voie qui n'est pas ouverte dans la mesure où le recours en matière de droit public est recevable. L'intitulé erroné d'un recours ne nuit cependant pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (cf. ATF 131 I 291 consid. 1.3 p. 296; 126 II 506 consid. 1b p. 509 et les arrêts cités). Encore faut-il qu'il soit possible de convertir le recours dans son ensemble; en effet, une conversion est exclue si certains griefs relèvent de la voie de droit choisie alors que d'autres devaient être soulevés dans un autre recours (ATF 134 III 379 consid. 1.2 p. 382; 131 III 268 consid. 6 p. 279). Dans la mesure où la Ville invoque des griefs d'ordre constitutionnel, notamment l'autonomie communale et l'arbitraire, ses moyens peuvent être soulevés dans un recours en matière de droit public. La conversion de ses deux recours dans son ensemble est possible et rien ne s'oppose à traiter les écritures déposées par la Ville comme des recours en matière de droit public.
2.2 Selon l'art. 89 al. 2 let. c LTF, les communes et autres collectivités publiques ont qualité pour recourir en invoquant la violation de garanties qui leur sont reconnues par les constitutions cantonale ou fédérale. La Ville invoque à maints égards l'autonomie qui lui est reconnue dans le domaine de la gestion du personnel. Il y a donc lieu de lui reconnaître la qualité pour agir sur la base déjà de cette disposition. La question de savoir si elle est réellement autonome dans le domaine considéré relève du fond (ATF 135 I 43 consid. 1.2 p. 45; 129 I 313 consid. 4.2 p. 319). Au reste, la Ville peut également agir sur la base de l'art. 89 al. 1 LTF, en tant qu'elle est touchée de manière analogue à un employeur privé (cf. ATF 134 I 204 consid. 2.3 p. 207).
II. Certificat de travail
3.1 3.1.1 Dans son recours contre l'arrêt du 21 juin 2011, la Ville se plaint d'arbitraire. Elle soutient que la chambre administrative n'était pas en droit de modifier son dispositif par la voie de l'interprétation. En effet, la demande en interprétation et en rectification comportait deux volets: une demande d'interprétation concernant les prétentions salariales de P._ et une demande de rectification du certificat de travail. Les conclusions du requérant en rapport avec sa demande d'interprétation ne visaient donc pas le certificat de travail. Or, les premiers juges seraient allés au-delà des conclusions du requérant en admettant de compléter le dispositif de leur arrêt sur la question du certificat par le biais de l'interprétation. Ce procédé serait contraire à l'art. 69 al. 1 de la loi cantonale genevoise sur la procédure administrative (LPA/GE; RS/GE E 5 10), selon lequel la juridiction administrative chargée de statuer est liée par les conclusions des parties.
3.1.2 Ce grief n'est pas fondé. S'il est vrai que l'interprétation se distingue de la rectification, quand bien même elles ne sont pas toujours réglées dans des dispositions légales séparées (voir p. ex. l'art. 129 LTF et l'ancien art. 145 OJ; cf. POUDRET/SANDOZ-MONOD, Commentaire de la loi fédérale d'organisation judiciaire, vol. V, n. 1 ad art. 145), il n'en reste pas moins que P._ a présenté dans une seule et même écriture une demande en interprétation et en rectification. La juridiction cantonale a considéré à ce propos que l'interdiction du formalisme excessif commandait de traiter la demande de rectification (portant sur le certificat de travail) comme une demande en interprétation. Ce procédé n'apparaît pas critiquable. Le principe constitutionnel invoqué pouvait assurément justifier de rechercher le sens de la démarche du requérant sans s'attacher nécessairement à la dénomination exacte dont il a pu se servir, en particulier dans l'intitulé de sa requête (voir aussi supra consid. 2.1)
3.1.2 Ce grief n'est pas fondé. S'il est vrai que l'interprétation se distingue de la rectification, quand bien même elles ne sont pas toujours réglées dans des dispositions légales séparées (voir p. ex. l'art. 129 LTF et l'ancien art. 145 OJ; cf. POUDRET/SANDOZ-MONOD, Commentaire de la loi fédérale d'organisation judiciaire, vol. V, n. 1 ad art. 145), il n'en reste pas moins que P._ a présenté dans une seule et même écriture une demande en interprétation et en rectification. La juridiction cantonale a considéré à ce propos que l'interdiction du formalisme excessif commandait de traiter la demande de rectification (portant sur le certificat de travail) comme une demande en interprétation. Ce procédé n'apparaît pas critiquable. Le principe constitutionnel invoqué pouvait assurément justifier de rechercher le sens de la démarche du requérant sans s'attacher nécessairement à la dénomination exacte dont il a pu se servir, en particulier dans l'intitulé de sa requête (voir aussi supra consid. 2.1)
3.2 3.2.1 La Ville soutient en outre que, même en admettant que la juridiction cantonale fût en droit de traiter la demande de rectification comme une demande d'interprétation, les conditions requises pour l'interprétation de son arrêt du 1er février 2011, relativement au certificat de travail, n'étaient de toute façon pas remplies. L'interprétation ne permettait pas, en l'espèce, de compléter le dispositif d'un jugement «par l'ajout de points qui n'existaient pas lors du dépôt de la demande en interprétation».
3.2.2 Selon l'art. 84 al. 1 LPA/GE, la juridiction qui a statué interprète sa décision, à la demande d'une partie, lorsqu'elle contient des obscurités ou des contradictions dans le dispositif ou entre le dispositif et les considérants. Les cas d'interprétation sont analogues à ceux prévus par l'art. 129 al. 1 LTF. D'après la jurisprudence relative à l'art. 129 LTF, à laquelle s'est référée la juridiction cantonale, l'interprétation tend à remédier à une formulation peu claire, incomplète, équivoque ou en elle-même contradictoire du dispositif de la décision rendue. Elle peut, en outre, se rapporter à des contradictions existant entre les motifs de la décision et le dispositif. Les considérants ne peuvent cependant faire l'objet d'une interprétation que si et dans la mesure où il n'est possible de déterminer le sens du dispositif qu'en ayant recours aux motifs. Ne sont pas recevables les demandes d'interprétation qui tendent à la modification du contenu de la décision ou à un nouvel examen de la cause. L'interprétation a en effet uniquement pour objet de reformuler clairement et complètement une décision qui n'a pas été formulée de façon distincte et accomplie alors même qu'elle a été clairement et pleinement pensée et voulue. Il n'est pas admissible de provoquer, par la voie ou la demande d'interprétation, une discussion d'ensemble de la décision entrée en force relative, par exemple, à la conformité au droit ou à la pertinence de celle-ci (voir par ex. arrêt 5G_1/2008 du 17 novembre 2008 consid. 1.1; PIERRE FERRARI, Commentaire de la LTF, 2009, n. 4 s. ad art. 129 LTF).
3.2.3 Au considérant 20 de son arrêt du 1er février 2011, la chambre administrative invite la Ville à établir un nouveau certificat de travail «conforme à la proposition faite par Monsieur P._ lors de l'audience de comparution personnelle». L'injonction ne figurait pas dans le dispositif, qui était donc incomplet. Un dispositif doit en effet être considéré comme incomplet lorsque le tribunal a omis d'exprimer dans celui-ci la décision prise (POUDRET/SANDOZ-MONOD, op. cit. vol. V, n. 3.1 ad art. 145). Dans sa décision d'interprétation, la juridiction aurait certes pu se contenter de transposer dans le dispositif le passage cité du considérant 20. Au lieu de cela, elle a inséré directement et textuellement le contenu de la proposition faite lors de l'audience de comparution personnelle. Cette manière de faire, qui ne modifie pas le contenu de la décision rendue tel qu'il a été voulu par les premiers juges, ne procède pas d'une application insoutenable de la réglementation cantonale en matière d'interprétation.
3.3 Invoquant la garantie de l'autonomie communale, la Ville soutient que l'établissement d'un certificat de travail relève de sa compétence exclusive. On ne voit toutefois pas au juste en quoi cette autonomie aurait été violée dans le cas concret. A partir du moment où le juge est saisi d'un litige sur le contenu d'un certificat de travail, il lui appartient de statuer sur la question litigieuse et, par conséquent, d'ordonner, au besoin, une modification du certificat dans un sens donné.
3.4 Enfin, dans ses deux recours, la Ville s'en prend au contenu des modifications apportées par les premiers juges, qui, selon elle, ne refléteraient pas la réalité des fonctions exercées par P._. Ce faisant, la Ville ne fait que se livrer à une critique appellatoire, en substituant son appréciation à celle de la juridiction précédente, sans démontrer l'arbitraire d'une manière qui satisfasse, tant soit peu, aux exigences de motivation de l'art. 106 al. 2 LTF et sans invoquer la violation d'un autre droit constitutionnel.
3.5 Le recours dans la cause 8D_2/2002 doit ainsi être rejeté.
III. Prétentions salariales
4. En ce qui concerne les prétentions salariales qui font l'objet de l'arrêt du 1er février 2011, la Ville soulève un certain nombre de griefs d'ordre procédural.
4. En ce qui concerne les prétentions salariales qui font l'objet de l'arrêt du 1er février 2011, la Ville soulève un certain nombre de griefs d'ordre procédural.
4.1 4.1.1 Elle reproche tout d'abord à la juridiction cantonale de s'être déclarée compétente dans un domaine où la loi ne lui attribue aucune compétence. Selon elle, les fonctionnaires n'ont aucun droit à un avancement ou une promotion. Ces questions ne peuvent donc pas faire l'objet d'une décision administrative. La juridiction cantonale ne pouvait donc se saisir du litige dans un domaine qui n'appelait pas de décision.
4.1.2 En droit public, la notion de «décision» au sens large vise habituellement toute résolution que prend une autorité et qui est destinée à produire un certain effet juridique ou à constater l'existence ou l'inexistence d'un droit ou d'une obligation; au sens étroit, c'est un acte qui, tout en répondant à cette définition, intervient dans un cas individuel concret (ATF 135 II 328 consid. 2.1 p. 331). Selon la teneur de l'art. 4 al. 1 LPA/GE, sont considérées comme des décisions les mesures individuelles et concrètes prises par l'autorité dans les cas d'espèce fondées sur le droit public fédéral, cantonal, communal, ayant pour objet: de créer, de modifier ou d'annuler des droits ou des obligations (let. a); de constater l'existence ou l'inexistence ou l'étendue de droits, d'obligations ou de faits (let. b); de rejeter ou de déclarer irrecevables des demandes tendant à créer, modifier, annuler ou constater des droits ou des obligations (let. c). Cette disposition définit la notion de décision de la même manière que l'art. 5 al. 1 de la loi fédérale du 20 décembre 1968 sur la procédure administrative (PA). La notion de décision implique donc un rapport juridique obligatoire et contraignant entre l'autorité et l'administré. En revanche, de simples déclarations, comme des opinions, des communications, des prises de position, des recommandations ou des renseignements n'entrent pas dans la catégorie des décisions, faute de caractère juridique contraignant. Ne sont pas non plus des décisions les actes internes ou d'organisation qui visent les situations à l'intérieur de l'administration; il peut y avoir des effets juridiques, mais ce n'en est pas l'objet. C'est pourquoi ils ne sont en règle ordinaire pas susceptibles de recours (voir par ex. l'arrêt 8C_191/2010 du 12 octobre 2010 consid. 6.1 et les références citées). L'acte par lequel une administration se prononce sur des prétentions salariales d'un employé en relation avec la classification d'une fonction répond indéniablement à la notion de décision. Contrairement à ce que suggère la Ville, le caractère décisionnel d'une mesure ne dépend pas d'un intérêt juridiquement protégé de son destinataire. Un intérêt de fait peut suffire (cf. PIERRE MOOR, Droit administratif, vol. II, 2002, n. 2.1.2.2 p. 162; cf. également l'arrêt 8C_191/2010, précité, consid. 6.3). Le point de savoir si les prétentions émises sont ou non justifiées est une question qui relève du fond et non de la procédure. Le grief soulevé ici est dès lors infondé.
4.1.2 En droit public, la notion de «décision» au sens large vise habituellement toute résolution que prend une autorité et qui est destinée à produire un certain effet juridique ou à constater l'existence ou l'inexistence d'un droit ou d'une obligation; au sens étroit, c'est un acte qui, tout en répondant à cette définition, intervient dans un cas individuel concret (ATF 135 II 328 consid. 2.1 p. 331). Selon la teneur de l'art. 4 al. 1 LPA/GE, sont considérées comme des décisions les mesures individuelles et concrètes prises par l'autorité dans les cas d'espèce fondées sur le droit public fédéral, cantonal, communal, ayant pour objet: de créer, de modifier ou d'annuler des droits ou des obligations (let. a); de constater l'existence ou l'inexistence ou l'étendue de droits, d'obligations ou de faits (let. b); de rejeter ou de déclarer irrecevables des demandes tendant à créer, modifier, annuler ou constater des droits ou des obligations (let. c). Cette disposition définit la notion de décision de la même manière que l'art. 5 al. 1 de la loi fédérale du 20 décembre 1968 sur la procédure administrative (PA). La notion de décision implique donc un rapport juridique obligatoire et contraignant entre l'autorité et l'administré. En revanche, de simples déclarations, comme des opinions, des communications, des prises de position, des recommandations ou des renseignements n'entrent pas dans la catégorie des décisions, faute de caractère juridique contraignant. Ne sont pas non plus des décisions les actes internes ou d'organisation qui visent les situations à l'intérieur de l'administration; il peut y avoir des effets juridiques, mais ce n'en est pas l'objet. C'est pourquoi ils ne sont en règle ordinaire pas susceptibles de recours (voir par ex. l'arrêt 8C_191/2010 du 12 octobre 2010 consid. 6.1 et les références citées). L'acte par lequel une administration se prononce sur des prétentions salariales d'un employé en relation avec la classification d'une fonction répond indéniablement à la notion de décision. Contrairement à ce que suggère la Ville, le caractère décisionnel d'une mesure ne dépend pas d'un intérêt juridiquement protégé de son destinataire. Un intérêt de fait peut suffire (cf. PIERRE MOOR, Droit administratif, vol. II, 2002, n. 2.1.2.2 p. 162; cf. également l'arrêt 8C_191/2010, précité, consid. 6.3). Le point de savoir si les prétentions émises sont ou non justifiées est une question qui relève du fond et non de la procédure. Le grief soulevé ici est dès lors infondé.
4.2 4.2.1 La Ville reproche ensuite aux premiers juges d'être entrés en matière sur le fond, alors qu'aucune décision formelle n'avait été rendue au préalable. A ce propos, la juridiction cantonale aurait retenu à tort l'existence d'un déni de justice dès lors qu'à maintes reprises la Ville a pris position par écrit sur les prétentions de son employé. Enfin, celui-ci aurait agi tardivement, plus de trois ans s'étant écoulés entre sa première mise en demeure et le dépôt de son recours.
4.2.2 La juridiction cantonale était incontestablement fondée à considérer que le refus de la Ville de rendre une décision en bonne et due forme était constitutif d'un déni de justice.
En cas de déni de justice, l'autorité saisie renvoie la cause à l'autorité défaillante en l'invitant à rendre une décision car, en principe, elle ne peut pas statuer elle-même directement sur le fond à la place de l'autorité qui est restée passive (cf. BERNARD CORBOZ, in: Commentaire de la LTF, 2009, n. 16 ad art. 94; FELIX UHLMANN, in: Niggli/Uebersax/ Wiprächtiger [éd.], Kommentar zum Bundesgerichtsgesetz, 2ème éd., n. 8 ad art. 94; MARKUS MÜLLER, in: Auer/Müller/Schindler [éd.], Kommentar zum Bundesgesetz über das Verwaltungsverfahren [VwVG], 2008, n° 14 ad art. 46a; en ce qui concerne plus particulièrement la procédure genevoise, voir THIERRY TANQUEREL, Manuel de droit administratif, 2011, n. 1503 p. 502; art. 69 al. 4 LPA/GE). Ce n'est qu'à titre exceptionnel, pour des raisons d'économie de la procédure, que l'autorité saisie peut entrer en matière sur le fond (FELIX UHLMANN/ SIMONE WÄLLE-BÄR, in: Waldmann/Weissenberger [éd.], VwVG, Praxiskommentar zum Bundesgesetz über das Verwaltungsverfahren, 2009, n. 37 ad art. 46a).
En l'espèce, ces conditions exceptionnelles apparaissent réalisées au regard du principe de l'économie de la procédure. En effet, dans ses déterminations à l'autorité cantonale du 15 juillet 2010, la Ville a fait valoir que si le tribunal administratif venait à considérer que X._ devait rendre une décision, alors la réponse de X._ du 5 mai 2010 devait être interprétée comme une décision négative en application de l'art. 4 al. 1 LPA/GE. Elle ne saurait se plaindre maintenant de ce que la chambre administrative est entrée en matière sur le fond.
Quant à l'argumentation selon laquelle l'intéressé aurait agi tardivement, elle paraît plutôt relever du droit de fond (prescription, renonciation à faire valoir un droit) et non des règles de procédure. Finalement, la Ville - qui s'étend longuement sur ces questions de procédure - ne démontre pas en quoi les premiers juges auraient appliqué de manière arbitraire les règles de procédure cantonale ni quels principes constitutionnels auraient été violés dans ce cas.
Quant à l'argumentation selon laquelle l'intéressé aurait agi tardivement, elle paraît plutôt relever du droit de fond (prescription, renonciation à faire valoir un droit) et non des règles de procédure. Finalement, la Ville - qui s'étend longuement sur ces questions de procédure - ne démontre pas en quoi les premiers juges auraient appliqué de manière arbitraire les règles de procédure cantonale ni quels principes constitutionnels auraient été violés dans ce cas.
4.3 4.3.1 Tout aussi longuement, la Ville soutient que l'autorité précédente a violé son autonomie. En résumé, le tribunal aurait librement réévalué le traitement de son ex-employé à compter du 1er mars 2005. Ce faisant, il aurait outrepassé ses compétences, notamment en faisant totale abstraction des processus d'évaluation prévus à cet effet par la réglementation communale. En d'autres termes, la juridiction cantonale se serait arrogé des compétences qui relèvent du domaine de la Ville en portant atteinte au mécanisme d'évaluation des fonctions propre à son organisation.
4.3.2 Dans la mesure où son autonomie est en cause, la commune peut exiger que l'autorité cantonale respecte les limites de sa compétence et qu'elle applique correctement les dispositions du droit fédéral, cantonal ou communal qui règlent la matière. L'autonomie communale doit cependant s'exercer dans les limites de la loi et en particulier le respect des principes généraux de droit public, notamment les droits constitutionnels (voir par ex. l'arrêt 1C_312/2010 du 8 décembre 2010 consid. 3.5, publié in PJA 2011 p. 698). Dans le cas particulier, l'autonomie invoquée n'a pas été méconnue par la juridiction cantonale. Celle-ci a fondé son jugement, comme on le verra ci-après, sur le droit constitutionnel à la protection de la bonne foi, l'interdiction de l'arbitraire, le respect du principe de l'égalité de traitement et l'abus de droit. La Ville peut alors faire valoir que l'autorité a méconnu la portée d'un droit fondamental et considéré à tort que celui-ci avait été violé.
5. 5.1 Les premiers juges constatent que dès le mois de mars 2005, P._ a assuré la gestion de la section V._ et a assisté son supérieur hiérarchique dans la direction et la coordination du secteur Z._ (comprenant la section A._, celle de Y._, ainsi que la formation Z._). Dès le 1er février 2008, il a remplacé complètement son supérieur jusqu'au 31 mars 2009 en accomplissant toutes les tâches en relation avec la fonction de ce dernier. En conséquence, la Ville devait lui verser, pour la période du 1er février au 31 décembre 2008 un traitement correspondant à celui de la classe 19 annuité 0 et du 1er janvier au 31 mars 2009 un traitement équivalant à la classe 19 annuité 1, avec intérêts à 5 % dès le 13 janvier 2010, sous déduction du salaire et des indemnités de remplacement perçus durant cette période. En outre, une classe de traitement supplémentaire - soit la classe 13 annuité 0 - aurait dû être accordée à l'intéressé dès le 1er mars jusqu'au 31 décembre 2005 et la classe 13 annuité 1 pour l'année 2006, puis la classe 13 annuité 2 du 1er janvier au 30 juin 2007, P._ demeurant au bénéfice de droits acquis concernant la classe 13 annuité 7 du 1er juillet au 31 décembre 2007. De ces montants devront être déduits le salaire et les indemnités de remplacement obtenus du 1er mars 2005 au 31 décembre 2007.
5. 5.1 Les premiers juges constatent que dès le mois de mars 2005, P._ a assuré la gestion de la section V._ et a assisté son supérieur hiérarchique dans la direction et la coordination du secteur Z._ (comprenant la section A._, celle de Y._, ainsi que la formation Z._). Dès le 1er février 2008, il a remplacé complètement son supérieur jusqu'au 31 mars 2009 en accomplissant toutes les tâches en relation avec la fonction de ce dernier. En conséquence, la Ville devait lui verser, pour la période du 1er février au 31 décembre 2008 un traitement correspondant à celui de la classe 19 annuité 0 et du 1er janvier au 31 mars 2009 un traitement équivalant à la classe 19 annuité 1, avec intérêts à 5 % dès le 13 janvier 2010, sous déduction du salaire et des indemnités de remplacement perçus durant cette période. En outre, une classe de traitement supplémentaire - soit la classe 13 annuité 0 - aurait dû être accordée à l'intéressé dès le 1er mars jusqu'au 31 décembre 2005 et la classe 13 annuité 1 pour l'année 2006, puis la classe 13 annuité 2 du 1er janvier au 30 juin 2007, P._ demeurant au bénéfice de droits acquis concernant la classe 13 annuité 7 du 1er juillet au 31 décembre 2007. De ces montants devront être déduits le salaire et les indemnités de remplacement obtenus du 1er mars 2005 au 31 décembre 2007.
5.2 5.2.1 P._ se plaint d'une violation du principe de l'interdiction de l'arbitraire. Il fait valoir qu'en statuant sur sa prétention, la chambre administrative avait à l'évidence l'intention de lui donner largement gain de cause. Or, le jugement entrepris contient une contradiction interne. La Cour ne s'est pas rendue compte qu'en réalité elle avait condamné la Ville à payer des montants nuls, voire négatifs, compte tenu des salaires et indemnités déjà perçus, ce qui s'explique par le rôle des annuités dans le calcul du salaire dans une classe de l'échelle des traitements. Ainsi, toujours selon P._, en 2005, le salaire annuel en classe 13 annuité 0 était de 79'247 fr., soit un montant inférieur au salaire de la classe 12 annuité 7 qu'il a perçu, soit 93'997 fr. De même, en 2006, le salaire annuel de la classe 13 annuité 1 (83'523 fr.) était inférieur à celui de la classe 12 annuité 8 (98'454 fr.). En 2007, le salaire de la classe 13 annuité 2 (87'475 fr.) était inférieur à celui de la classe 12 annuité 8 (99'576 fr.).
5.2.2 Cette contradiction entre les motifs et le dispositif n'est pas contestée par la Ville. Quant aux premiers juges, ils l'ont spontanément admise dans leur arrêt du 21 juin 2011 sur interprétation et rectification. C'est ainsi qu'ils relèvent qu'en adoptant le dispositif de leur arrêt du 1er février 2011, ils ont voulu partiellement faire droit aux conclusions de P._. Ils admettent s'être trompés sur le résultat auquel conduisait le dispositif. Ils ont cependant refusé de modifier ce dispositif par la voie de l'interprétation pour les motifs suivants:
«Pour modifier le résultat, la chambre de céans devrait procéder à un réexamen de la cause, par des calculs et des comparaisons qui sortent du champ d'application de la demande d'interprétation (...). Un tel réexamen n'est possible que dans le cadre du contrôle juridictionnel exercé par l'autorité de recours. Il appartient ainsi au Tribunal fédéral, cas échéant, de constater l'illégalité de l'arrêt attaqué et de renvoyer la cause à la chambre administrative pour nouvel examen».
5.2.3 En principe, une contradiction flagrante - qui, comme en l'espèce, n'ouvre pas la voie de l'interprétation pour la résoudre - est constitutive d'arbitraire (arrêt 5P.126/2006 du 4 septembre 2006 consid. 4). Le jugement attaqué devrait donc être annulé et renvoyé à l'autorité cantonale pour qu'elle mette son dispositif en accord avec ce qu'elle a réellement voulu. En effet, même en interprétant l'arrêt du 1er février 2011 à la lumière de ses considérants, il est difficile, voire impossible, pour le Tribunal fédéral de déterminer ce que la juridiction cantonale voulait en réalité accorder à P._. On doit toutefois se demander, au préalable, s'il est possible de trancher la question litigieuse quant à son principe, à savoir la prétention de P._ à obtenir rétroactivement une collocation plus élevée dans l'échelle des traitements depuis 2005 et de renvoyer la cause à l'autorité cantonale pour qu'elle calcule exactement le montant qui lui reviendrait de ce chef. Comme on le verra, l'état de fait retenu par les premiers juges ne le permet toutefois pas.
5.2.3 En principe, une contradiction flagrante - qui, comme en l'espèce, n'ouvre pas la voie de l'interprétation pour la résoudre - est constitutive d'arbitraire (arrêt 5P.126/2006 du 4 septembre 2006 consid. 4). Le jugement attaqué devrait donc être annulé et renvoyé à l'autorité cantonale pour qu'elle mette son dispositif en accord avec ce qu'elle a réellement voulu. En effet, même en interprétant l'arrêt du 1er février 2011 à la lumière de ses considérants, il est difficile, voire impossible, pour le Tribunal fédéral de déterminer ce que la juridiction cantonale voulait en réalité accorder à P._. On doit toutefois se demander, au préalable, s'il est possible de trancher la question litigieuse quant à son principe, à savoir la prétention de P._ à obtenir rétroactivement une collocation plus élevée dans l'échelle des traitements depuis 2005 et de renvoyer la cause à l'autorité cantonale pour qu'elle calcule exactement le montant qui lui reviendrait de ce chef. Comme on le verra, l'état de fait retenu par les premiers juges ne le permet toutefois pas.
5.3 5.3.1 Dans la partie «en fait» de l'arrêt du 1er février 2011, la cour cantonale ne fait que résumer le contenu de son dossier, à savoir en particulier les pièces produites et les actes des parties. Dans la partie «en droit», elle s'est fondée sur le droit constitutionnel à la protection de la bonne foi pour admettre que P._ devait être rétribué correctement pour les fonctions qu'il avait effectivement assumées. Elle a estimé que les cinq conditions cumulatives qui président à la reconnaissance de ce droit étaient réalisées dans le cas d'espèce.
5.3.2 Sur ce point, les faits retenus par la juridiction cantonale se limitent à la constatation qu'à partir du 8 mars 2005, P._, ainsi que son supérieur hiérarchique, n'ont eu de cesse de demander une évaluation ou une réévaluation de la fonction de l'employé. Bien que les compétences de l'intéressé aient été reconnues, une analyse de fonction a été différée. Les premiers juges poursuivent en constatant qu'aucune de «ces démarches ni de ces promesses» n'a débouché sur un réexamen de la fonction de l'employé, qui a dû subir, en juillet 2008, une procédure d'«assessment» qui a conduit au dépôt d'un rapport élogieux pour l'intéressé. En août 2008, B._, adjoint à la direction générale, a fait «miroiter» à P._ la perspective de se voir attribuer le poste de coordinateur de V._ s'il faisait acte de candidature. Or, ce poste ne lui a finalement pas été attribué sous le faux prétexte, constatent les premiers juges, que l'épouse de l'intéressé exerçait également un poste à responsabilités au service Y._. La déduction que la juridiction cantonale en tire se trouve résumée dans le bref considérant suivant:
«En ne donnant pas suite aux demandes de réévaluation de sa fonction présentées par M. P._, appuyées par sa hiérarchie, en lui faisant miroiter l'expectative d'une nouvelle affectation à un poste supérieur puis en lui refusant celui-ci sous des prétextes qui se sont avérés inexacts, la Ville a contrevenu au principe de la bonne foi, les cinq conditions cumulatives précitées étant remplies. M. P._ a continué à travailler alors que l'incertitude entretenue par son employeur lui occasionnait des problèmes de santé, ce qui n'a pas été contesté».
5.3.3 Une telle conclusion méritait à tout le moins d'être étayée par quelques faits précis. L'examen des conditions qui président à la reconnaissance d'un avantage découlant du droit constitutionnel à la bonne foi (cf. p. ex. ATF 137 I 69 consid. 2.5.1 p.72) nécessitait un examen minutieux, qui fait totalement défaut en l'espèce. Ainsi le jugement attaqué ne précise pas, concrètement, quelles promesses l'intéressé aurait reçues quant à une modification de ses conditions salariales et, dans l'affirmative, à partir de quel moment ces promesses auraient dû se concrétiser. De plus, on ne voit pas, a priori, quel est le lien entre une éventuelle candidature au poste de coordinateur de V._ et les augmentations rétroactives de traitement à partir de 2005. Enfin, le jugement attaqué ne contient pas de faits qui permettraient d'admettre que P._ aurait pris, sur la base d'assurances qu'il aurait reçues, des dispositions sur lesquelles il ne pouvait revenir. En définitive, les premiers juges se sont contentés d'affirmations très générales, sans fournir de réelles explications et sans les confronter véritablement aux pièces du dossier. Cela a conduit la Ville recourante à se plaindre d'un établissement des faits manifestement incomplet et à invoquer nombre de faits qui ressortiraient du dossier et dont la juridiction cantonale n'aurait pas tenu compte.
5.3.4 Par ailleurs, il apparaît aussi que l'intéressé a perçu une indemnité mensuelle pour l'activité déployée durant la période pendant laquelle il a remplacé son supérieur hiérarchique. Les premiers juges considèrent que le versement de cette indemnité ne repose pas sur une base légale, mais sur une simple recommandation de X._, dont l'application aurait conduit, en l'espèce, à une décision choquante dans son résultat et, partant, arbitraire. Cette décision serait également contraire au principe de l'égalité de traitement et à l'interdiction de l'abus de droit. Sur ce point également, le jugement attaqué ne contient toutefois pas de faits qui permettraient de trancher. Ainsi, il n'est guère possible de qualifier de choquant le supplément mensuel alloué à P._ si l'on ignore ce que représenteraient les montants qui devraient, selon la juridiction cantonale, lui être réellement accordés sur la base du nouveau calcul qu'elle préconise. Enfin, en l'absence de faits constatés à ce propos, on ne sait pas non plus sur quels éléments de comparaison la juridiction cantonale s'est fondée pour admettre une inégalité de traitement.
5.3.5 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente selon l'art. 105 al. 1 LTF. Il ne lui appartient en principe pas, comme autorité de dernière instance de recours, d'instruire pour la première fois les faits pertinents. En particulier, il n'a pas à rechercher lui-même dans la partie «en fait» du jugement attaqué des éléments qui seraient déterminants pour la solution retenue. Cette partie du jugement, bien que détaillée, ne supplée pas une véritable appréciation des preuves permettant de savoir ce que les juges tiennent ou non pour avéré (voir arrêt 4A_408/2010 du 7 octobre 2010 consid. 2.1 non publié dans l'ATF 136 III 513). Si un état de fait est lacunaire et que la conformité de l'arrêt attaqué à la loi ou aux droits fondamentaux ne peut pas être contrôlée, celui-ci sera annulé et la cause renvoyée à l'autorité précédente, conformément à l'art. 107 al. 2 LTF, afin que l'état de fait soit complété (ATF 133 IV 293 consid. 3.4.2 p. 295).
C'est le cas en l'espèce.
5.3.6 Dans cette mesure les recours de chacune des parties doivent être admis dans les causes 8C_220/2011 et 8D_1/2011.
6. P._ obtient gain de cause en ce qui concerne le litige relatif à son certificat de travail. La Ville qui succombe sur ce point supportera une partie des frais judiciaires (art. 66 al. 1 LTF). Elle versera en outre à P._ une indemnité de dépens réduite (art. 68 al. 1 LTF).
Au regard des contradictions de l'arrêt du 1er février 2011 entre ses motifs et son dispositif, ainsi que du caractère lacunaire de la constatation des faits par la juridiction précédente, il se justifie de mettre le solde des frais de justice à la charge de l'Etat de Genève, qui supportera aussi la part des dépens en faveur de P._ non couverte par l'indemnité à la charge de la Ville (ATF 133 V 402 consid. 5 p. 407 et les références). Celle-ci ne peut pour sa part se voir accorder des dépens (art. 68 al. 3 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel subsidiaire de P._ dans la cause 8C_220/2011 est irrecevable.
2. Le recours de la Ville dirigé contre l'arrêt du 21 juin 2011, traité comme un recours en matière de droit public (cause 8D_2/2011), est rejeté.
3. Le recours en matière de droit public de P._ et le recours de la Ville, traité comme un recours en matière de droit public, tous deux dirigés contre l'arrêt du 1er février 2011 (causes 8C_220/2011 et 8D_1/2011) sont partiellement admis; cette décision est annulée et la cause renvoyée à la chambre administrative pour nouvelle décision, au sens des considérants, sur les prétentions salariales de P._.
4. Les frais judiciaires, arrêtés à 3'000 fr., sont mis pour 1'000 fr. à la charge de la Ville de Genève et pour 2'000 fr. à la charge du Canton de Genève.
5. Une indemnité de 6'000 fr. à payer pour 2'000 fr. par la Ville de Genève et pour 4'000 fr. par le Canton de Genève est allouée à P._.
6. Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lucerne, le 2 mars 2012
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
Le Greffier: Beauverd