Faits:
A. Le 10 janvier 2005, un contrat de bail à loyer d'une durée déterminée a été conclu entre G._ et la Ville de Genève, portant sur un logement social de trois pièces sis au 4ème étage de l'immeuble X._, propriété de la Ville. Le contrat stipulait qu'il débutait le 1er janvier 2005 pour se terminer trois mois après que les crédits nécessaires à la réhabilitation de l'immeuble auraient été acceptés par le Conseil municipal de la Ville.
G._ occupait déjà depuis plusieurs années les locaux sans droit. Son fils, M._ a vécu dans l'immeuble depuis le 1er janvier 2002.
B. Selon le procès-verbal de conciliation valant jugement d'évacuation du 15 février 2005, G._ s'est engagé à quitter l'appartement susmentionné dans le délai indiqué. A partir d'une date incertaine (1er avril 2009 ou 1er septembre 2009), M._ est demeuré seul dans l'appartement.
Auparavant, le 17 septembre 2008, le Conseil municipal de la Ville avait déposé une proposition en vue de l'ouverture d'un crédit destiné à la rénovation de l'immeuble X._.
Par lettre du 13 février 2009, la Ville a confirmé à l'Association genevoise de défense des locataires (ASLOCA) qu'elle était disposée à garantir aux locataires actuels de l'immeuble le retour dans le bâtiment après les travaux, moyennant la conclusion de baux de durée indéterminée et pour autant que chacun d'eux respecte les conditions posées par le nouveau règlement fixant les conditions de location des logements à caractère social de la Ville.
Par la suite, M._ a demandé à la Ville de lui attribuer, après rénovation, l'appartement qu'il occupait à l'immeuble X._. Le 7 décembre 2009, la Ville lui a fait savoir que la fondation Y._ (qui est une coopérative de logement pour personnes en formation) avait à disposition un studio dans le quartier pour un loyer mensuel de 350 fr. environ. M._ n'a pas donné suite à cette proposition. Ultérieurement, il a donné son accord à une proposition de la Ville de relogement provisoire dans un appartement de deux pièces à la rue A._.
Le 1er mars 2010, la Gérance Q._ a informé l'intéressé qu'elle refusait d'entrer en matière sur sa candidature pour la location d'un appartement dans l'immeuble X._ après les travaux, au motif qu'il était étudiant. Le contrat de bail pour l'appartement A._ lui était remis, avec la précision qu'il était de durée déterminée jusqu'au 30 novembre 2010, car l'immeuble était aussi promis à la rénovation. Le 16 mars 2010, la conseillère administrative du département des finances et du logement de la Ville a confirmé le refus de la Gérance Q._. Elle a accordé à M._ un dernier délai au 23 mars 2010 pour libérer l'appartement dans l'immeuble X._ et un autre délai, au 19 mars 2010, pour lui faire parvenir le contrat de bail signé pour l'appartement A._.
M._ a pris possession de l'appartement A._, tout en déclarant son intention de retourner dans son logement au l'immeuble X._ après les travaux de rénovation. Le 6 juillet 2010, il a requis de la Ville qu'elle reconsidère sa décision du 16 mars 2010 relative au refus d'entrer en matière sur son relogement dans cet immeuble.
Le 14 septembre 2010, la Gérance Q._ a déclaré que le département maintenait sa position.
C. M._ a recouru contre cette décision devant le Tribunal administratif de la République et canton de Genève (depuis le 1er janvier 2011: la Chambre administrative de la Cour de justice). Il concluait notamment à ce que le tribunal ordonne à la Ville de lui attribuer un appartement de deux pièces dans l'immeuble X._ à la fin des travaux. Subsidiairement, il demandait au tribunal d'ordonner à la Ville de lui attribuer un appartement à caractère social convenable dans un des immeubles dont elle est propriétaire.
Statuant le 20 septembre 2011, la Chambre administrative a déclaré irrecevable une conclusion subsidiaire, prise en cours de procédure et tendant à ce que la Ville attribue à l'intéressé un appartement de deux pièces dans l'immeuble de la rue A._ à la fin des travaux. Elle a pour le reste rejeté le recours.
D. M._ exerce un recours en matière de droit public dans lequel il conclut à ce que le tribunal ordonne à la Ville de lui attribuer un appartement, principalement dans l'immeuble X._, subsidiairement A._, plus subsidiairement dans un des immeubles propriété de la Ville de Genève. Préalablement il demande l'attribution de l'effet suspensif.
La Ville de Genève conclut au rejet du recours.
Considérant en droit:
1. Le recours peut être interjeté notamment pour violation du droit fédéral (art. 95 let. a LTF), qui comprend les droits constitutionnels. En revanche, il ne peut être formé pour violation du droit cantonal en tant que tel; cependant, il est possible de faire valoir que l'application du droit cantonal est arbitraire ou contraire à d'autres droits constitutionnels (ATF 134 III 379 consid. 1.2 p. 382; 133 III 462 consid. 2.3 p. 466).
2. Le recourant conteste tout d'abord le refus des premiers juges d'entrer en matière sur sa conclusion subsidiaire tendant à l'attribution d'un logement de deux pièces a la rue A._ à la fin des travaux (et assortie d'une conclusion visant à le reloger pendant les travaux). Les premiers juges ont fait ici application de l'art. 65 al. 1 et 3 de la loi cantonale genevoise sur la procédure administrative (LPA-GE; RS/GE E 5 10), selon lequel les conclusions doivent être présentées dans l'acte de recours; elles ne peuvent être formulées après le délai de recours. Le recourant - qui se contente d'invoquer sans autres développements l'interdiction du formalisme excessif - ne démontre pas en quoi la solution arrêtée par les premiers juges serait contraire au droit fédéral. Sur ce point, le recours ne satisfait pas aux exigences de motivation de l'art. 106 al. 2 LTF.
3. A maints égards, le recourant se plaint d'un établissement des faits manifestement inexact ou incomplet. Conformément à l'art. 105 al. 1 LTF, le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente. L'art. 105 al. 2 LTF lui permet cependant de rectifier ou compléter d'office les constatations de l'autorité précédente si les faits ont été établis de manière manifestement inexacte ou en violation du droit au sens de l'art. 95 LTF. Cette disposition vise en particulier la violation de l'interdiction constitutionnelle de l'arbitraire (ATF 134 V 53 consid. 4.3 p. 62). Il appartient à la partie recourante de démontrer cette violation, par une argumentation répondant aux exigences de motivation de l'art. 42 al. 2 LTF, respectivement de l'art. 106 al. 2 LTF. Le recourant allègue que l'état de fait de l'arrêt attaqué ne tient pas compte de nombreux éléments, qui sont susceptibles d'influer sur l'issue du litige. Il n'établit pas que ceux-ci étaient d'une importance telle qu'une éventuelle omission devrait être qualifiée d'arbitraire. Au demeurant, de prime abord, on ne voit guère que les allégations du recourant soient de nature à remettre en cause la solution de l'autorité précédente. Dans ces conditions, il n'y a pas lieu de compléter ou de rectifier l'état de fait retenu dans la décision attaquée.
4. 4.1 Le recourant se plaint d'une violation des art. 11 par. 1 du Pacte international relatif aux droits économiques, sociaux et culturels (Pacte ONU I; RS 0.103.1), 12 Cst. et 10B de la Constitution de la République et canton de Genève (Cst-GE; RS/GE A 2 00).
4.2 Selon l'art. 12 Cst., quiconque est dans une situation de détresse et n'est pas en mesure de subvenir à son entretien a le droit d'être aidé et assisté et de recevoir les moyens indispensables pour mener une existence conforme à la dignité humaine. Ce droit fondamental à des conditions minimales d'existence ne garantit toutefois pas un revenu minimum, mais uniquement la couverture des besoins élémentaires pour survivre d'une manière conforme aux exigences de la dignité humaine, tels que la nourriture, le logement, l'habillement et les soins médicaux de base (ATF 135 I 119 consid. 5.3 p. 123). Dans le canton de Genève, ce principe a trouvé une concrétisation dans la loi sur l'insertion et l'aide sociale individuelle du 22 mars 2007 (LIASI; RS/GE J 4 04), qui garantit à toute personne majeure qui en fait la demande de pouvoir bénéficier d'un accompagnement social (art. 5 al. 1 LIASI) et à toute personne qui n'est pas en mesure de subvenir à son entretien ou à celui des membres de la famille dont elle a la charge de bénéficier de prestations d'aide financière (art. 8 LIASI).
4.3 Dans le cas particulier, le recourant ne prétend pas des prestations au titre de l'aide sociale - qui comprennent, en particulier, un hébergement d'urgence - et on ne voit dès lors pas en quoi les garanties déduites de l'art. 12 Cst. s'appliqueraient à sa situation. Le recourant n'établit pas qu'il n'a pas la possibilité d'obtenir un logement décent. Du reste, la Ville lui a fait des propositions de relogement. Ce qu'il veut, en réalité, c'est qu'elle lui accorde un appartement dans un immeuble déterminé ou un logement social propriété de la Ville. Comme telle, cette prétention ne relève pas de l'art. 12 Cst.
4.4 Le recourant ne prétend par ailleurs pas que l'art. 10B Cst-GE - qui consacre un droit au logement - lui accorderait le droit revendiqué.
4.5 Quant à l'art. 11 du Pacte ONU I, il prévoit que les Etats parties reconnaissent le droit de toute personne à un niveau de vie suffisant pour elle-même et sa famille, y compris une nourriture, un vêtement et un logement suffisants, ainsi qu'à une amélioration constante de ses conditions d'existence; les Etats prendront des mesures appropriées pour assurer la réalisation de ce droit et ils reconnaissent à cet effet l'importance essentielle d'une coopération internationale librement consentie (par. 1). Le Tribunal fédéral a jugé à plusieurs reprises que les dispositions de ce pacte énonçaient un programme, s'adressaient au législateur et ne conféraient en principe pas aux particuliers de droits subjectifs que ceux-ci pouvaient invoquer en justice (cf. en dernier lieu ATF 136 I 290 consid. 2.3.1 p. 293). Dans le cas particulier, il apparaît que la disposition invoquée s'adresse au législateur, respectivement au Constituant, lequel a notamment édicté l'art. 12 Cst. et au législateur cantonal, qui a en l'espèce adopté la LIASI. Au demeurant, le recourant ne démontre pas en quoi cette disposition du pacte lui accorderait des droits plus étendus que l'art. 12 Cst.
4.6 Les griefs soulevés ici par le recourant se révèlent mal fondés.
5. 5.1 Le recourant se plaint d'une violation de l'art. 8 al. 1 Cst. en tant que l'arrêt attaqué retient qu'il ne peut se voir attribuer l'appartement de deux pièces vacant dans l'immeuble X._, parce qu'il n'était pas lui-même locataire avant le début des travaux. Le recourant voit par ailleurs une discrimination du fait de son âge (art. 8 al. 2 Cst.) au motif que l'arrêt attaqué retient que l'une des conditions d'octroi d'un logement à caractère social est l'existence d'un groupe familial ou, à tout le moins, une certaine indépendance financière du locataire, dont ne bénéficie pas un étudiant. Le recourant cite le cas d'une personne qui a obtenu un contrat de bail dans l'appartement rénové de l'immeuble X._, bien qu'il ait interrompu son activité professionnelle pour se consacrer à des études. Pour les mêmes motifs, la décision attaquée serait entachée d'arbitraire (art. 9 Cst.).
5.2 La protection de l'égalité (art. 8 Cst.) et celle contre l'arbitraire (art. 9 Cst.) sont étroitement liées. Une norme est arbitraire lorsqu'elle ne repose pas sur des motifs sérieux ou si elle est dépourvue de sens et de but (ATF 136 I 241 consid. 3.1 p. 250). Elle viole le principe de l'égalité de traitement consacré à l'art. 8 al. 1 Cst. lorsqu'elle établit des distinctions juridiques qui ne se justifient par aucun motif raisonnable au regard de la situation de fait à réglementer ou qu'elle omet de faire des distinctions qui s'imposent au vu des circonstances, c'est-à-dire lorsque ce qui est semblable n'est pas traité de manière identique et ce qui est dissemblable ne l'est pas de manière différente (ATF 134 I 23 consid. 9.1 p. 42). Au principe d'égalité de traitement, l'art. 8 al. 2 Cst. ajoute une interdiction des discriminations. Selon cette disposition, nul ne doit subir de discrimination du fait notamment de son origine, de sa race, de son sexe, de son âge, de sa langue, de sa situation sociale, de son mode de vie, de ses convictions religieuses, philosophiques ou politiques ni du fait d'une déficience corporelle, mentale ou physique. On est en présence d'une discrimination selon l'art. 8 al. 2 Cst. lorsqu'une personne est traitée différemment en raison de son appartenance à un groupe particulier qui, historiquement ou dans la réalité sociale actuelle, souffre d'exclusion ou de dépréciation. Le principe de non-discrimination n'interdit toutefois pas toute distinction basée sur l'un des critères énumérés à l'art. 8 al. 2 Cst., mais fonde plutôt le soupçon d'une différenciation inadmissible. Aussi bien des inégalités qui résultent d'une telle distinction doivent-elles faire l'objet d'une justification particulière (ATF 137 V 334 consid. 6.2.1 p. 348; 135 I 49 consid. 4.1 p. 53).
5.3 En l'espèce, le recourant perd de vue - comme l'ont retenu les premiers juges - qu'il n'était pas lui-même locataire d'un appartement de l'immeuble en question. Seul son père était titulaire d'un contrat de bail. Il semble d'ailleurs que celui-ci ait obtenu à ce titre d'être relogé dans ce même immeuble après les travaux. Le fait de ne reloger que les personnes au bénéfice d'un contrat de bail n'est assurément pas contraire au principe d'égalité de traitement. S'agissant du cas cité par le recourant, les premiers juges retiennent que cette personne (assistant social de profession) a entrepris une formation en cours d'emploi (Master en travail social). Sa situation n'est pas identique à celle du recourant. Enfin, comme le relèvent les premiers juges, les dispositions du Règlement du conseil municipal du 18 février 2009 fixant les conditions de location des logements à caractère social de la Ville de Genève (LC 21 531) prévoient de fixer le loyer en fonction du " revenu familial ", ce qui tend à démontrer que l'attribution d'un logement à caractère social de la Ville ne vise en principe pas les étudiants, du moins pas ceux d'entre eux qui n'ont pas de charges de familles et pour lesquels il existe d'autres possibilités de logement plus spécifiques (sous-location d'une chambre, colocation, foyers, coopérative de logement pour personnes en formation etc.). Même s'il est notoire que les étudiants pâtissent d'une pénurie de logements à Genève, au même titre d'ailleurs que la population en général, une telle distinction n'est nullement incompatible avec le principe de l'égalité de traitement et l'interdiction de la discrimination.
6. 6.1 Le recourant se plaint enfin d'une violation de son droit d'être entendu. Il fait grief aux premiers juges de n'avoir pas procédé à l'administration de preuves qu'il a proposées. En particulier, il leur reproche de ne pas avoir requis la production de nombre de documents (par exemple la copie des contrats de bail et les procès-verbaux valant jugement d'évacuation pour les locataires de l'immeuble X._, les documents relatifs à la planification de la date d'ouverture du chantier de la rue des Étuves, ainsi que divers autres documents). De même, il fait grief à la juridiction précédente de n'avoir pas procédé à l'audition de plusieurs témoins. Enfin, la Cour de justice aurait écarté deux pièces qu'il a produites au motif qu'elles ont été déposées après que la cause a été gardée à juger le 12 mai 2011.
6.2 Le droit de faire administrer des preuves suppose que le fait à prouver soit pertinent et que le moyen de preuve proposé soit nécessaire pour constater ce fait et que la demande soit présentée selon les formes et délais prescrits (cf. ATF 134 I 140 consid. 5.3 p. 148). Par ailleurs, cette garantie n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude qu'elles ne pourraient l'amener à modifier son opinion (cf. ATF 130 II 425 consid 2.1 p. 429).
6.3 En l'espèce, comme le recourant n'était pas locataire dans l'immeuble X._, il ne pouvait prétendre à être relogé dans ce bâtiment. Comme on l'a vu, cette solution n'est pas contraire aux principes constitutionnels invoqués par le recourant. Les preuves proposées n'étaient pas de nature à établir des faits qui permettaient de juger autrement les questions de droit soulevées par le litige. Les premiers juges pouvaient donc se dispenser de les administrer. Quant aux pièces écartées du dossier, le recourant ne démontre pas qu'elles auraient été présentées selon les formes et les délais requis par le droit cantonal.
7. De ce qui précède, il résulte que le recours est mal fondé. Les frais de la cause doivent être mis à la charge du recourant (art. 66 al. 1 LTF). La Ville de Genève n'a pas droit à des dépens (art. 68 al. 3 LTF).
8. La cause étant tranchée, la requête d'effet suspensif devient sans objet.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué aux parties et à la Chambre administrative de la Cour de justice de la République et canton de Genève.
Lucerne, le 20 juin 2012
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
Le Greffier: Beauverd