Faits:
A. A.a A._, né en 1949, a été engagé le 1er mai 1977 par le Département de la sécurité, de la police et de l'environnement (ci-après: DSPE) du canton de Genève - anciennement nommé département de justice et police, puis département des institutions - en qualité de contrôleur de passeports aéroport-gare. L'intéressé a été nommé à cette fonction par le Conseil d'Etat le 12 novembre 1980. Il a ensuite été promu par le Conseil d'Etat, à compter du 1er juillet 1981, à la fonction de contrôleur police frontière puis, à compter du 1er juillet 1991, à celle de chef de groupe police frontière. Il était soumis à la loi générale relative au personnel de l'administration cantonale du 15 octobre 1987 et à son règlement d'application du 7 décembre 1987 ainsi qu'à la loi concernant le traitement et les diverses prestations alloués aux membres du personnel de l'Etat et des établissements hospitaliers du 21 décembre 1973 (ci-après: LTrait) et à son règlement d'application du 17 octobre 1979 (ci-après: RTrait).
Le 9 janvier 1997, la police frontière (PF) a été intégrée au sein du détachement des gardes d'aéroport (DGA), lesquels étaient armés pour leur service. Leurs missions étaient décrites aux art. 2 et 3 du Règlement concernant le détachement de gardes d'aéroport du 29 juin 1988 (RDGA). L'intégration des membres de la PF dans le détachement des gardes de l'aéroport a fait l'objet d'une modification de ce règlement, lequel a été complété, le 18 décembre 1996, par une disposition transitoire (art. 12) qui précisait que les contrôleurs de frontière et les chefs de groupe affectés auprès du service de la PF conservaient leur statut et ne bénéficiaient pas des soins médicaux gratuits. Il était également mentionné que les collaborateurs de la police frontière n'étaient pas armés et qu'ils n'assuraient qu'une partie des tâches attribuées aux gardes d'aéroport.
A.b En 2001, une profonde restructuration de la police de l'aéroport a notamment conduit à la création de la police de la sécurité internationale (ci-après: PSI), laquelle regroupe le détachement des gardes de l'aéroport (DGA) et les gardes de sécurité diplomatiques (GSD). Le statut des agents de la PSI a fait l'objet d'un règlement spécifique (Règlement relatif à la police de la sécurité internationale, du 13 juin 2001 [RPSI]; RSG F 1 05.21), entré en vigueur le 15 juillet 2001, lequel a remplacé le RDGA du 29 juin 1988.
A cette époque, le DSPE a proposé aux membres de la PF de devenir agents de la PSI et subordonné cette intégration à une évaluation psychologique et à la prise de cours de tir, les agents de la PSI étant armés pour leur service. Seuls deux membres de la PF ont accepté la proposition et ont suivi avec succès la formation nécessaire pour devenir agent de la PSI. A._ n'a, quant à lui, pas donné suite à cette proposition.
A.c Une refonte importante de la loi sur la police du 26 octobre 1957 (LPol; RSG F 1 05) a été adoptée le 27 août 2004 et est entrée en vigueur au 1er janvier 2005. Se fondant sur les art. 43A ss de cette loi, le Conseil d'Etat a adopté une nouvelle version du RPSI le 16 février 2005, qui est entré en vigueur rétroactivement au 1er février 2005. Comme dans son ancienne teneur, cette nouvelle version prévoit une disposition transitoire (art. 13), aux termes de laquelle les contrôleurs de frontière et les chefs de groupe affectés auprès du service de la PF sont intégrés à la PSI. Ils conservent toutefois leur statut antérieur et n'assurent que les tâches visées à l'article 2, lettres b et c du règlement.
A._ ainsi que cinq autres fonctionnaires faisant encore partie de la PF ont demandé au Conseil d'Etat leur intégration pleine et entière dans la PSI pour pouvoir bénéficier du même statut que les agents PSI. Une procédure d'intégration a alors été mise en place par le DSPE. Le passage d'une visite médicale complète avec évaluation psychologique ainsi qu'une formation de tir ont été exigés des candidats. A._ ayant fait l'objet d'un préavis «très peu favorable» de la part du médecin-conseil de l'Etat en raison, notamment, de son obésité et d'un passé médical important, son intégration à la PSI a été refusée par le DSPE, sans qu'aucun recours ne soit ouvert contre cette décision.
A._ a contesté ce refus devant le DSPE. Le 22 janvier 2009, il a ouvert une action devant le Tribunal administratif du canton de Genève (aujourd'hui: Chambre administrative de la Cour de justice), demandant à bénéficier des mêmes avantages que les agents de la PSI, soit notamment le paiement de ses primes d'assurance-maladie ainsi qu'une indemnité pour inconvénients de service, pour les cinq dernières années, correspondant à un montant total de 71'921 fr. 65 plus intérêts à 5 % l'an. Par arrêt du 3 novembre 2009, le Tribunal administratif a déclaré cette action irrecevable, en raison de l'absence de décision préalable prise par le DSPE.
Par décision du 23 décembre 2009, le DSPE a rejeté les prétentions de A._.
B. A._ a recouru contre cette décision devant le Tribunal administratif en concluant à son annulation, à ce que l'Etat de Genève soit condamné à lui payer la somme de 71'921 fr. 65 avec intérêts à 5 % dès le 30 juin 2006, ainsi qu'à l'octroi d'une indemnité de procédure.
Le 5 février 2010, A._ a démissionné de ses fonctions pour le 31 décembre 2010.
Par jugement du 2 novembre 2010, le Tribunal administratif a rejeté le recours.
C. A._ interjette un recours en matière de droit public en concluant à l'annulation du jugement attaqué. Principalement, il demande la constatation de son droit à diverses prestations prévues par la loi sur la police, et la condamnation de l'Etat de Genève à lui payer la somme de 71'921 fr. 65 avec intérêts à 5 % dès le 30 juin 2006, sous réserve d'amplification, le tout sous suite de frais et dépens. Subsidiairement, il conclut au renvoi de la cause à la juridiction cantonale pour qu'elle l'instruise sous l'angle du principe de l'égalité de traitement qu'il avait invoqué dans la procédure cantonale.
Le Conseil d'Etat conclut au rejet du recours.

Considérant en droit:
1. 1.1 Le recours en matière de droit public n'est pas recevable contre les décisions en matière de rapports de travail de droit public qui concernent une contestation non pécuniaire, sauf si elles touchent à la question de l'égalité des sexes (art. 83 let. g LTF). S'agissant de contestations pécuniaires, pour que le recours soit recevable, il faut encore que la valeur litigieuse atteigne le seuil minimal de 15'000 fr. (<ref-law>). En l'occurrence, la contestation porte sur une créance de plus de 70'000 fr. Le seuil de la valeur litigieuse déterminante est donc largement dépassé.
1.2 Pour le surplus, interjeté en temps utile (<ref-law>) contre une décision finale (<ref-law>) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF), le recours en matière de droit public est rece-vable.
2. Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 p. 400; <ref-ruling> consid. 1.1 p. 104). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 2.2.1 p. 389; <ref-ruling> consid. 1.4 p. 400).
Par exception à la règle selon laquelle il applique le droit d'office, le Tribunal fédéral ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
3. 3.1 Le recourant invoque une violation des principes de la légalité et de la séparation des pouvoirs au motif que l'art. 13 al. 2 RPSI ne respecte pas le cadre de la délégation prévue par l'art. 43A LPol. Il fait également valoir que la disposition réglementaire est contraire aux art. 43B et 43C LPol.
3.2 Le respect du principe de la légalité dans le cadre d'une délégation de compétence législative découle du principe de la séparation des pouvoirs (<ref-ruling> consid. 2a p. 309) et doit normalement être invoqué en relation avec ce dernier (<ref-ruling> consid. 2.1 p. 326; <ref-ruling> consid. 2.1 p. 162 s.).
Le principe de la séparation des pouvoirs est garanti, au moins implicitement, par toutes les constitutions cantonales; il représente un droit constitutionnel dont peut se prévaloir le citoyen. Sans être expressément consacré en droit genevois (sauf en ce qui concerne l'indépendance du pouvoir judiciaire, posée à l'art. 130 Cst./GE), le principe de la séparation des pouvoirs découle notamment de l'art. 116 Cst./GE, selon lequel le Conseil d'État promulgue les lois, est chargé de leur exécution et prend à cet effet les règlements et arrêtés nécessaires (<ref-ruling> consid. 2.2 et 2.3 p. 326 s.; <ref-ruling> consid. 5.2).
Ce principe assure le respect des compétences établies par la constitution cantonale. Il appartient donc en premier lieu au droit public cantonal de fixer les compétences des autorités. Le principe de la séparation des pouvoirs interdit à un organe de l'État d'empiéter sur les compétences d'un autre organe; en particulier, il interdit au pouvoir exécutif d'édicter des règles de droit, si ce n'est dans le cadre d'une délégation valablement conférée par le législateur. L'ordonnance d'exécution ne peut disposer qu'intra legem et non pas praeter legem. Elle peut établir des règles complémentaires de procédure, préciser et détailler certaines dispositions de la loi, éventuellement combler de véritables lacunes; mais, à moins d'une délégation expresse, elle ne peut poser des règles nouvelles qui restreindraient les droits des administrés ou leur imposeraient des obligations, même si ces règles sont encore conformes au but de la loi (<ref-ruling> consid. 4.2 p. 279; <ref-ruling> consid. 2.2 p. 326). Le Tribunal fédéral examine sous l'angle restreint de l'arbitraire l'interprétation des dispositions en matière de compétence qui figurent dans les lois cantonales (ATF <ref-ruling> consid. 5.2 p. 317).
3.3 Appelé à revoir l'interprétation d'une norme sous l'angle restreint de l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si celle-ci apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs et en violation d'un droit certain. En revanche, si l'application de la loi défendue par l'autorité cantonale ne s'avère pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation en cause, cette interprétation sera confirmée, même si une autre solution - éventuellement plus judicieuse - paraît possible (<ref-ruling> consid. 1.2 p. 177).
3.4 Alors que le Tribunal administratif a jugé que le Conseil d'Etat n'avait pas outrepassé la délégation de l'art. 43A LPol en édictant l'art. 13 RPSI, le recourant fait valoir que l'art. 43A LPol délègue au Conseil d'Etat notamment les tâches de fixer par voie réglementaire l'organisation de la PSI et les conditions d'engagement mais ne fait aucunement mention d'une compétence du Conseil d'Etat pour déroger au régime légal en matière de statut et de traitement à l'égard des membres de la PF. Or, en prévoyant que les contrôleurs de frontière et les chefs de groupe affectés auprès du service de la PF conservent leur statut antérieur, sans pouvoir bénéficier des mêmes avantages que les agents de la PSI en matière de statut et de traitement, l'art. 13 al. 2 RPSI prévoit, selon le recourant, un régime dérogatoire pour les membres de la PF, non prévu dans la clause de délégation de l'art. 43A LPol et de surcroît contraire aux art. 43B et 43C LPol.
4. 4.1 L'art. 43A LPol autorise le Conseil d'Etat à fixer par règlement «les missions et l'organisation de la police de la sécurité internationale, ainsi que les conditions d'engagement et de promotion de ses agents». Fondé sur cette disposition légale, le Conseil d'Etat a édicté le RPSI, notamment l'art. 13 dont la teneur est la suivante:
1 «Les contrôleurs de frontière et les chefs de groupe affectés auprès du service de la police frontière sont intégrés à la police de la sécurité internationale.
2 Ils conservent leur statut antérieur.
3 Ils n'assurent que les tâches visées à l'article 2, lettres b et c, du présent règlement».
Quant aux art. 43B et 43C LPol, ils prévoient que, sous réserve de l'application par analogie de certaines dispositions de la LPol aux agents de la PSI, ceux-ci sont soumis aux dispositions de la loi générale relative au personnel de l'administration cantonale, du pouvoir judiciaire et des établissements publics médicaux, du 4 décembre 1997 (LPAC) - laquelle a remplacé la loi générale relative au personnel de l'administration cantonale du 15 octobre 1987 -, respectivement de la LTrait.
4.2 Selon le RPSI, la PSI est organisée militairement (art. 6 al. 1 RPSI). Elle comprend les grades énumérés exhaustivement à l'art. 6 al. 2 RPSI. Les membres de la PF ne figurent pas dans la liste de l'art. 6 RPSI. Ils ne sauraient en tout cas pas être assimilés aux «agents» de la PSI mentionnés à l'art. 6 al. 2 let. h RPSI puisqu'aux termes de l'art. 7 al. 1 RPSI, ces derniers portent un uniforme et sont armés pour leur service, ce qui n'est pas le cas des membres de la PF. Quant aux tâches exercées par les membres de la PF, elles ne sont pas identiques à celles assumées par les agents de la PSI. En effet, l'art. 13 al. 3 RPSI attribue aux agents de la PF une partie seulement des missions exercées par les agents de la PSI, à savoir celles visées à l'art. 2, let. b et c RPSI. Le recourant a d'ailleurs indiqué, dans son mémoire de réplique devant la juridiction cantonale, que les membres de la PF approchant l'âge de la retraite étaient cantonnés dans du travail de bureau, soit essentiellement l'octroi de visas et la délivrance de passeports, tâches correspondant au demeurant à celles visées par l'art. 2 let. b et c RPSI. Ainsi, bien qu'ayant été formellement intégrés à la PSI, les membres de la PF qui n'ont pas suivi la formation pour devenir agent de la PSI et ne portent par conséquent pas d'arme, n'exercent que certaines tâches dévolues aux agents de la PSI. Cette différence dans l'étendue des tâches exercées justifie, à l'instar de ce qu'ont retenu les premiers juges, une différence de statut entre les membres de la PF et les agents de la PSI.
4.3 Il reste à examiner s'il existe une base légale suffisante pour autoriser le Conseil d'Etat à maintenir un statut particulier pour les membres de la PF. On a vu que l'art. 43A LPol chargeait notamment le Conseil d'Etat de fixer par règlement l'organisation de la PSI et les conditions d'engagement de ses agents. Il n'est pas arbitraire de soutenir, comme l'a jugé le Tribunal administratif, que l'art. 13 al. 2 RPSI relève de l'organisation au sens de l'art. 43A LPol. Contrairement à ce que soutient le recourant, les questions d'organisation ne se limitent pas nécessairement à des questions liées à la hiérarchie, au port d'arme ou encore à l'horaire de travail traitées aux art. 6 à 8 RPSI. Elle laisse en tout cas une certaine latitude à l'autorité exécutive qui n'interdit pas, a priori, de régler différemment le statut d'agents qui, bien qu'intégrés dans un même corps, n'exécutent pas les mêmes tâches que les agents de la PSI. Au reste, on arrive à un même résultat si l'on considère que la délégation du législateur donne aussi au Conseil d'Etat la compétence de fixer les conditions d'engagement des agents de la PSI. Comprise dans un sens large, la notion de «conditions d'engagement» inclut non seulement les conditions personnelles ou subjectives que doit remplir un agent ou un fonctionnaire de l'Etat mais se réfère généralement aussi à son statut et/ou son traitement. Il ne serait en tout cas pas insoutenable d'admettre que les questions ayant trait au statut et au traitement d'une personne font partie des conditions d'engagement de celles-ci. Compte tenu de ce qui précède, les premiers juges n'ont pas fait preuve d'arbitraire en considérant que l'art. 13 al. 2 RPSI était couvert par la clause de délégation de l'art. 43A LPol. Il n'y a pas lieu d'examiner ici plus en détails quel est le statut et le traitement auxquels renvoie l'art. 13 al. 2 RPSI puisque les premiers juges ont traité cette question et que leur argumentation n'est pas remise en cause par le recourant.
Enfin, dans la mesure où le Conseil d'Etat pouvait prévoir un statut différent pour les membres de la PF, l'art. 13 RPSI ne viole pas les art. 43B et 43C LPol et l'argumentation contraire du recourant sur ce point est par conséquent sans objet.
5. Selon le recourant, les premiers juges ont par ailleurs violé son droit d'être entendu en refusant, sans motifs, de donner suite à ses offres de preuves destinées à prouver que les tâches qui lui avaient été dévolues au fil des ans excédaient largement celles auxquelles renvoie l'art. 13 al. 3 RPSI.
5.1 Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend notamment pour le justiciable le droit de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'obtenir l'administration des preuves pertinentes et valablement offertes, de participer à l'administration des preuves essentielles et de se déterminer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.1 p. 277; <ref-ruling> consid. 2a/aa p. 16; <ref-ruling> consid. 3a p. 51). Par ailleurs, même si la procédure administrative est régie essentiellement par la maxime inquisitoire, les parties ont le devoir de collaborer à l'établissement des faits (<ref-ruling> consid. 2b p. 142) et l'autorité peut mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction (<ref-ruling> consid. 2.1 p. 429 et les arrêts cités).
5.2 En l'occurrence, il ressort des preuves disponibles au dossier que le recourant n'exerce plus les diverses missions énumérées à titre d'offres de preuve. Selon l'intimé, ces tâches ne seraient plus exercées depuis une quinzaine d'années. Comme on l'a vu, le recourant a lui-même indiqué dans son mémoire de réplique devant la juridiction cantonale que depuis son intégration à la PSI, il était cantonné dans du travail de bureau. Par conséquent, dans la mesure où ses offres de preuve se rapportent à des tâches exercées avant l'entrée en vigueur du RPSI au 1er février 2005, elles sont sans pertinence pour l'issue de la cause. Le refus du Tribunal administratif de procéder à l'administration de telles preuves procède ainsi d'une appréciation anticipée des preuves. Partant, le grief de la violation du droit d'être entendu est infondé et doit être rejeté.
6. Les considérants qui précèdent conduisent au rejet du recours.
Succombant, le recourant doit supporter les frais de la procédure (<ref-law>). Il n'est pas alloué d'indemnité de dépens à l'intimé (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3. 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 29 septembre 2011
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Ursprung
La Greffière: Fretz Perrin