Faits:
A. Pendant plusieurs années, B._, C._, D._ et A._ ont fait le commerce de glaces, boissons et petite restauration dans des stands dont ils étaient propriétaires, ouverts de façon saisonnière et situés sur le pourtour de la rade de Genève. A ce titre, ils s'acquittaient annuellement d'une taxe d'utilisation accrue du domaine public, perçue par la Ville de Genève (ci-après: la ville). F._ et E._ étaient dans la même situation, mais faisaient le commerce de souvenirs.
La revalorisation du site de la rade a conduit la ville et l'Etat de Genève à une réflexion conjointe dès 2001. Celle-ci a abouti à l'idée d'une uniformisation des divers stands de glaciers et de souvenirs. En outre, la ville envisageait de modifier le régime d'exploitation préexistant, car elle souhaitait détenir son mobilier urbain. Elle appliquerait dorénavant un régime de location et non plus d'utilisation du domaine public. Le 22 juin 2009, le Conseil municipal de la ville a adopté le projet correspondant.
Le 24 juillet 2009, la ville a publié un appel «d'offres pour la location de huit pavillons saisonniers amovibles sur le pourtour de la rade de Genève destinés à des glaciers», ainsi qu'un autre pour quatre pavillons de commerce de souvenirs. Elle proposait de louer aux personnes physiques intéressées, pour cinq saisons consécutives, du 1er mars au 31 octobre de chaque année, un pavillon, contre un loyer compris entre ***** et ***** fr. par saison, comprenant la redevance liée à une permission saisonnière de l'usage du domaine public, calculée sur la base d'un tarif de ** fr. le m2. Pour les vendeurs de souvenirs, le montant du loyer aux mêmes conditions était de **** fr. Le cahier des charges précisait que les baux mobiliers distingueraient les montants dus à titre de loyer et ceux dus à titre de redevance pour l'utilisation du domaine public.
B. En date du 20 janvier 2010, B._, C._, D._ et A._ ont chacun conclu avec la ville un contrat de bail à loyer par lequel celle-ci mettait à leur disposition un pavillon saisonnier destiné à l'exploitation d'un commerce de glaces, boissons et petite restauration. Le 21 janvier 2010, F._ et E._ ont signé avec la ville un contrat similaire, prévoyant la mise à disposition d'un pavillon saisonnier servant à exploiter un commerce de souvenirs. Tous ces contrats prévoyaient que la ville louait un pavillon amovible dont elle était propriétaire. Celui-ci était installé à un emplacement déterminé pour lequel le locataire était mis au bénéfice d'une permission saisonnière d'utilisation du domaine public. La saison d'exploitation commençait le 1er mars et s'achevait le 31 octobre de chaque année. Pour les pavillons de glaciers, le loyer variait entre ***** et près de ***** fr. par saison. Pour ceux de vente de souvenirs, le loyer s'élevait à **** fr. Les contrats précisaient que le locataire devrait en outre s'acquitter d'une redevance pour l'utilisation du domaine public, à concurrence de ** fr. le m2, taxe sur la valeur ajoutée en sus.
Par décisions séparées datées du 1er septembre 2010, la ville a accordé à B._, C._, D._, F._, E._ et A._ une permission d'utilisation du domaine public à titre précaire pour la période allant du 1er mars au 31 octobre 2010. Pour les exploitants des pavillons de glaciers, le montant de la taxe était compris entre **** et **** fr. S'agissant des pavillons de vente de souvenirs, la taxe s'élevait à **** fr.
C. Par actes séparés du 13 octobre 2010, B._, C._, D._, F._, E._ et A._ ont recouru à l'encontre de ces décisions auprès de la Commission cantonale de recours en matière administrative, devenue le 1er janvier 2011 le Tribunal administratif de première instance (ci-après: le TAPI), en contestant notamment la compétence de la ville pour délivrer une autorisation d'usage accru du domaine public et percevoir une redevance à ce titre.
Par jugement du 30 mai 2011, le TAPI a prononcé la jonction des procédures et a admis partiellement les recours, sur des points qui ne sont plus litigieux en l'espèce. Il a rejeté les recours pour le surplus, en retenant notamment que, selon la jurisprudence cantonale, le régime de la location pouvait coexister avec celui de l'autorisation pour usage accru du domaine public.
Le 4 juillet 2011, les prénommés ont recouru à l'encontre du jugement précité auprès de la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice), qui les a déboutés par arrêt du 20 mars 2012.
D. B._, C._, D._, F._, E._ et A._ interjettent un recours en matière de droit public auprès du Tribunal fédéral contre l'arrêt de la Cour de justice du 20 mars 2012. Ils requièrent de l'annuler en tant qu'il confirme la perception d'une taxe pour l'utilisation accrue du domaine public, sous suite de dépens.
La Cour de justice persiste dans les considérants et les motifs de son arrêt, alors que la ville conclut au rejet du recours, dans les limites de sa recevabilité, sous suite de frais et dépens.

Considérant en droit:
1. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle donc librement la recevabilité des recours qui sont déposés devant lui (<ref-ruling> consid. 1 p. 472, 436 consid. 1 p. 438 et les arrêts cités).
1.1 Interjeté en temps utile et dans les formes requises, contre une décision finale prise en dernière instance cantonale par une autorité judiciaire supérieure, par les destinataires de cette décision, le recours en matière de droit public, qui ne tombe sous aucune des exceptions de l'<ref-law>, est en principe recevable au regard des art. 42 et 82 ss LTF.
1.2 D'après l'<ref-law>, le Tribunal fédéral applique le droit d'office. Par conséquent, sous réserve des exigences de motivation figurant aux art. 42 al. 2 et 106 al. 2 LTF, il examine en principe librement l'application du droit fédéral. En revanche, la mauvaise application du droit cantonal n'est pas en elle-même un motif de recours. A cet égard, l'intéressé peut en principe seulement se plaindre d'arbitraire dans l'application du droit cantonal. Lorsqu'il soulève un tel grief, le recourant ne peut toutefois se contenter de critiquer la décision attaquée, comme il le ferait dans une procédure d'appel où l'autorité supérieure peut revoir librement l'application du droit cantonal, mais il doit préciser en quoi cette décision serait insoutenable, ne reposerait sur aucun motif sérieux et objectif, ou encore heurterait gravement le sens de la justice (cf. <ref-ruling> consid. 1.2 p. 145; <ref-ruling> consid. 1.3 p. 59).
2. Les recourants estiment d'abord que la perception d'une taxe pour usage accru du domaine public serait contraire à la liberté économique garantie par l'art. 27 al. 1 Cst.
Il incombait aux recourants d'exposer de manière précise (cf. consid. 1.2 ci-dessus) en quoi la liberté économique garantie par l'art. 27 al. 1 Cst. ferait obstacle à la perception de la taxe litigieuse, car on ne voit a priori pas en quoi le fait de cumuler une taxe pour l'utilisation accrue du domaine public et un loyer constituerait une restriction inadmissible de la liberté en question. Au lieu de cela, les recourants se contentent d'affirmer l'existence d'une telle violation, avant d'émettre des considérations étrangères à cette problématique. Tel que formulé, le grief est donc irrecevable.
3. Les recourants dénoncent ensuite l'arbitraire de l'arrêt entrepris, en se prévalant de l'art. 9 Cst.
A nouveau, leur approche est purement appellatoire, les recourants n'exposant pas en quoi il serait insoutenable que deux prestations, fondées l'une sur le droit du bail fédéral et l'autre sur la législation cantonale relative à l'utilisation du domaine public, donnent lieu à des contre-prestations cumulées de la part du cocontractant au bénéfice d'un droit d'usage accru du domaine public. Derechef, le grief est irrecevable.
4. Au vu de ce qui précède, le recours est irrecevable. Succombant, les recourants supporteront, solidairement entre eux, les frais de la procédure devant le Tribunal fédéral (cf. art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3. Le présent arrêt est communiqué au mandataire des recourants, à la Ville de Genève, Service de la sécurité et de l'espace publics, et à la Cour de justice du canton de Genève, Chambre administrative.
Lausanne, le 1er octobre 2012
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Vianin