Faits:
A. Par un appel d'offres publié dans la Feuille d'avis officielle (FAO) du 26 juin 2006, la Ville de Genève (ci-après: la Ville) a mis en soumission le renouvellement de la concession d'affichage papier sur son domaine public pour la période allant du 1er janvier 2008 au 31 décembre 2012. Selon les conditions énoncées dans l'appel d'offres et précisées dans le dossier de candidature remis aux participants, le marché, "soumis OMC", devait être attribué en un seul lot selon une procédure à deux tours, le premier portant sur la sélection des candidats selon des critères d'aptitude, le second sur l'adjudication proprement dite du marché; par ailleurs, il était prévu que la sélection des candidats aurait lieu le 30 octobre 2006 et que la décision de sélection serait susceptible de recours devant le Tribunal administratif du canton de Genève (ci-après: le Tribunal administratif) dans un délai de 10 jours dès sa publication; enfin, le chiffre 5.1 du dossier de candidature précisait que les règles en matière de marchés publics seraient applicables à la procédure d'appel d'offres, "quand bien même il [n'était] pas acquis, à teneur de la jurisprudence, que l'attribution du marché de l'affichage sur le domaine public de la Ville de Genève [fût] soumise au droit des marchés publics".
La société X._ SA, à B._ (ci-après: la Société), a déposé un dossier de candidature, tout en contestant la procédure d'appel d'offres par le moyen de deux recours, l'un devant le Tribunal administratif, l'autre devant le Tribunal fédéral. Pour l'essentiel, elle soutenait que le marché litigieux devait être divisé en lots et réparti entre plusieurs concessionnaires, car son attribution à une seule entreprise aboutissait à la création d'un monopole de fait contraire à la liberté économique et à l'égalité entre concurrents.
A.a Le Tribunal fédéral a suspendu la procédure portée devant lui (classée sous la cause 2P.210/2006) jusqu'à droit connu sur le recours parallèle formé au Tribunal administratif.
A.b Par arrêt du 19 décembre 2006, le Tribunal administratif a déclaré irrecevable le recours dont il était saisi, faute de décision attaquable. Il a en effet considéré que l'octroi d'une concession de monopole d'affichage publicitaire sur le domaine public n'était, selon la jurisprudence du Tribunal fédéral, pas soumise à la réglementation sur les marchés publics, si bien que les voies de droit prévues en cette matière pour contester un appel d'offres n'étaient pas applicables. Par ailleurs, à supposer qu'il pût être assimilé à une décision incidente, l'appel d'offres litigieux ne pouvait, selon les juges cantonaux, pas être attaqué à ce stade de la procédure, car il n'était pas de nature à causer un préjudice juridique irréparable à la Société; le moment venu, cette dernière pourrait en effet librement soumettre ses griefs au Tribunal administratif dans le cadre d'un recours formé contre la décision d'attribution.
La Société a déféré l'arrêt précité du Tribunal administratif devant le Tribunal fédéral (cause 2P.51/2007), en se plaignant de la violation du principe de la bonne foi et d'arbitraire dans l'application du droit de procédure genevois.
A.c Par arrêt du 4 juillet 2007, après avoir ordonné la reprise de l'instruction dans la cause 2P.210/2006 et avoir joint celle-ci à la cause 2P.51/2007, le Tribunal fédéral a déclaré irrecevable le recours formé dans la première des procédures précitées et rejeté celui formé dans la seconde. Dans la première cause, il a estimé, à l'instar du Tribunal administratif, que compte tenu de sa nature incidente, l'appel d'offres ne pouvait pas faire l'objet d'un recours de droit public, car il n'était pas susceptible de causer un préjudice juridique irréparable à la Société. Dans la seconde cause, il a jugé que le Tribunal administratif n'avait pas violé le droit à la protection de la bonne foi de la Société en refusant d'entrer en matière sur son recours, en ce sens que l'indication par erreur d'une voie de droit inexistante n'était pas de nature à en créer une.
B. Entre-temps, le 3 novembre 2006, la Société a été informée qu'elle avait été sélectionnée aux côtés d'un autre soumissionnaire, soit la Société Y._, à C._, pour participer au second tour de l'appel d'offres. Le 2 mars 2007, la Ville a communiqué aux deux candidats retenus les documents relatifs à cette nouvelle phase de la procédure, dont un dossier de procédure et un cahier des charges assortis de leurs annexes.
A réception des documents précités, la Société a derechef saisi le Tribunal administratif d'un recours. Elle critiquait en particulier les chiffres 10 et 19 du cahier des charges qui imposaient au concessionnaire, d'une part, de fournir à la Ville des prestations d'affichage gratuites sur le "réseau genevois" (ville et canton) et sur le "réseau suisse et/ou international" et, d'autre part, d'assurer la mise en place et la gestion d'un système dit de vélos en libre service selon des modalités précises détaillées dans un descriptif. Au vu de la nature et de l'ampleur de ces prestations, la Société estimait que la procédure avait désormais toutes les caractéristiques d'un marché public dont les conditions pouvaient être contestées en justice lors de l'appel d'offres déjà, conformément aux dispositions réglant le contentieux en ce domaine du droit.
La Ville a conclu au rejet du recours.
Par arrêt du 20 mai 2008, le Tribunal administratif a déclaré le recours irrecevable, en reprenant la motivation développée dans sa précédente décision du 19 décembre 2006 concernant l'inapplicabilité des règles en matière de marchés publics au cas, ainsi que l'absence de décision (incidente) de nature à causer un préjudice irréparable à la Société (cf. supra ad A.b).
C. La Société forme un recours en matière de droit public contre l'arrêt précité du Tribunal administratif. Elle se plaint de constatation manifestement inexacte et incomplète des faits pertinents, de motivation insuffisante de l'arrêt attaqué et de violation de la réglementation applicable en matière de marchés publics. Elle soutient, comme en instance cantonale, que les règles en matière de marchés publics sont applicables à la présente procédure, si bien que les documents litigieux remis lors du second tour de l'appel d'offres doivent être assimilés à des décisions attaquables. Elle conclut, sous suite de dépens, à l'annulation de l'arrêt entrepris et au renvoi de la cause au Tribunal administratif pour instruction complémentaire et décision sur le fond du recours. A titre préalable, elle requiert l'octroi de l'effet suspensif.
A titre provisoire, le Tribunal fédéral a autorisé la Ville à reprendre et poursuivre la procédure d'appel d'offres à l'exception de l'attribution de la concession pour l'affichage sur le domaine public et de la conclusion du contrat d'adjudication.
La Ville de Genève conclut, sous suite de frais et dépens, au rejet de la requête d'effet suspensif ainsi qu'à l'irrecevabilité du recours, subsidiairement à son rejet. Le Tribunal administratif s'en remet à justice quant à la requête d'effet suspensif et à la recevabilité du recours; sur le fond, il déclare persister dans les considérants et le dispositif de son arrêt.
Considérant en droit:
1. Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF); il revoit donc librement la recevabilité des recours qui lui sont soumis (ATF 133 I 185 consid. 2 p. 188 et les arrêts cités).
1.1 La décision attaquée déclare irrecevable le recours déposé par X._ SA à l'encontre du second tour d'appel d'offres de la Ville de Genève. Les juges ont estimé que la réglementation spéciale des voies de droit prévue pour les marchés publics n'était pas applicable, dès lors qu'il s'agissait d'une concession. La recourante soutient que le système de vélos en libre service que le concessionnaire doit mettre à disposition de la Ville conformément au chiffre 19 du cahier des charges (du 2 mars 2007) justifierait l'application des règles sur les marchés publics à l'ensemble des opérations, subsidiairement uniquement aux prestations ayant trait au système de vélos en libre service et, partant, lui ouvrirait le droit de recourir sur le plan cantonal. La recourante ne motive la recevabilité de son recours devant le Tribunal fédéral qu'en regard des prestations exigées en relation avec le système de vélos en libre service qui ne figuraient pas dans le dossier de candidature, mais ont été introduites dans le cahier des charges précité remis aux candidats lors du second tour de l'appel d'offres. L'objet du litige porté devant le Tribunal fédéral se limite donc au point de savoir si les prestations exigées de l'intimée en relation avec la mise à disposition d'un système de vélos en libre service emportent l'application du droit des marchés publics et, plus particulièrement, des garanties procédurales propres à ce droit.
1.2 La cause relève du droit public (art. 82 let. a LTF). L'arrêt attaqué émane d'un tribunal cantonal supérieur statuant en dernière instance, sans qu'un recours auprès du Tribunal administratif fédéral ne soit ouvert (art. 86 al. 1 let. d et al. 2 LTF). Il peut donc en principe faire l'objet d'un recours en matière de droit public au Tribunal fédéral, à condition qu'il ne tombe pas sous le coup de l'une des exceptions prévues à l'art. 83 LTF, en particulier l'art. 83 let. f LTF. Selon cette disposition, le recours en matière de droit public n'est recevable contre les décisions en matière de marchés publics qu'à deux conditions, soit si la valeur du mandat à attribuer est supérieure ou égale aux seuils déterminants prévus à cet effet et si, cumulativement, la décision attaquée soulève une question juridique de principe (ATF 134 II 192 consid. 1.2 p. 194 s.). Il incombe au recourant, sous peine d'irrecevabilité, de démontrer la réalisation de ces deux conditions (cf. ATF 133 II 396 consid. 2.2 p. 398 s.).
1.3 La présente cause à ceci de particulier que, pour savoir si l'art. 83 let. f LTF est applicable, il faut au préalable déterminer si l'on est bien en présence d'un marché public. Or, cette question constitue précisément l'objet du litige porté devant le Tribunal fédéral (cf. supra consid. 1.1). L'examen de la recevabilité du recours suppose donc de résoudre une question qui se recoupe avec le fond du litige. Dans un tel cas, il suffit, au stade de la recevabilité, que le recourant rende vraisemblable que, sur la question litigieuse, les conditions fondant la compétence du tribunal sont remplies, le point de savoir si tel est effectivement le cas étant ensuite tranché, pour autant que les autres conditions de recevabilité soient réunies, avec l'examen de la cause au fond (cf., dans un contexte analogue, la théorie dite de la double pertinence développée en droit international privé, ATF 131 III 153 consid. 5. 1 et les arrêts cités).
En l'espèce, la recourante invoque des éléments de fait et de droit de nature à rendre plausible l'application du droit des marchés publics à la présente procédure (sur ces éléments, cf. notamment infra consid. 1.3.2). Dans cette mesure, il y a lieu d'examiner si son recours échappe à la clause d'irrecevabilité prévue à l'art. 83 let. f LTF en matière de marchés publics, soit de vérifier si le marché atteint les valeurs seuils déterminantes (infra consid. 1.3.1) et si le recours soulève une question juridique de principe (infra consid. 1.3.2). Conformément à l'art. 42 al. 2 LTF, il incombe à la recourante d'exposer en quoi ces condition sont réalisées, sous peine d'irrecevabilité de son recours (cf. ATF 134 III 354 précité; 133 III 439 consid. 2.2.2.1; 133 II 396 consid. 2.2 p. 398 s.).
1.3.1 Les valeurs seuils prévues dans la loi fédérale du 16 décembre 1994 sur les marchés publics (LMP; RS 172.056.1) s'élevaient, lors du dépôt du recours au Tribunal fédéral, à 248'950 fr., aussi bien pour les marchés de fournitures que pour les marchés de services (cf. ATF 134 II 192 consid. 1.3 p. 195 s.; art. 1er let. a et b de l'ordonnance du DFE du 26 novembre 2007 sur l'adaptation des valeurs seuils des marchés publics pour l'année 2008 - RO 2007 6627).
La recourante fait valoir que la mise en place et la gestion du système de vélos en libre service pour la durée de la concession correspond à des prestations d'une valeur approximative d'un million et demi de francs, ce que la Ville conteste, mais sans donner d'indication démontrant le caractère surfait de ce montant. Compte tenu des importantes prestations exigées de l'intimée pour ce poste (cf. infra consid. 5.2.1), il paraît acquis, même en l'absence d'évaluation précise, que la valeur minimale imposée par la législation est atteinte.
1.3.2 L'existence d'une question juridique de principe s'apprécie en fonction du contenu de l'objet litigieux soumis au Tribunal fédéral (cf. ATF 134 II 192 consid. 1.3 p. 195) et doit n'être admise que de manière restrictive. Ainsi, lorsque le point soulevé ne concerne que l'application de principes jurisprudentiels à un cas particulier, il ne peut être qualifié de question juridique de principe (ATF 134 III 115 consid. 1.2 p. 117). La seule circonstance que la question n'ait encore jamais été tranchée ne suffit pas non plus à réaliser cette condition. Il faut encore qu'il s'agisse d'une question juridique dont l'importance pratique est telle qu'elle nécessite d'être éclaircie par la plus haute instance judiciaire (cf. arrêts 2C_107/2007 du 22 janvier 2008, consid. 1.1 et 2C_116/2007 du 10 octobre 2007, consid. 4.2). A l'inverse, il peut arriver qu'une question déjà résolue par le Tribunal fédéral revête néanmoins la qualité d'une question juridique de principe. Tel est notamment le cas si la jurisprudence rendue sur le sujet n'est pas claire ou n'est pas constante ou si elle suscite d'importantes critiques dans la doctrine (cf. ATF 134 III 354 consid. 1.3 p. 357 et les nombreuses références citées).
En l'espèce, dans un arrêt publié in ATF 125 I 209, le Tribunal fédéral avait jugé qu'une procédure tendant à l'octroi d'une concession portant sur un monopole d'affichage ne présentait pas les éléments caractéristiques d'un marché public. Cette jurisprudence a été critiquée par une partie de la doctrine (sur ce point, cf. infra consid. 4.3). De plus, elle ne permet pas d'emblée d'exclure l'application du droit des marchés publics à certaines prestations requises en annexe de la concession d'affichage ici en cause. Enfin, contrairement à ce que prétend la Ville, le Tribunal fédéral n'a pas déjà statué sur cette question dans l'arrêt du 4 juillet 2007 rendu entre les parties au présent litige lors du premier tour de l'appel d'offres (causes jointes 2P.210/2006 et 2P.51/2007). Avec la recourante, il faut en effet admettre que les documents litigieux remis aux candidats lors du second tour de l'appel d'offres ont modifié de manière importante les conditions initiales du marché, en prévoyant pour le concessionnaire l'obligation de mettre en place et d'exploiter le système litigieux de vélos en libre service. Il se justifie dès lors d'examiner si ces éléments nouveaux ont, selon les termes de la recourante, changé "radicalement l'équilibre économique et financier de l'opération, [au point que] le cahier des charges [aurait] maintenant toutes les caractéristiques d'un véritable marché public". Dans cette mesure, la question de savoir si le droit des marchés publics s'applique ou non dans le cas d'espèce revêt une portée de principe au sens de l'art. 83 let. f ch. 2 LTF.
1.3.3 Par conséquent, le recours en matière de droit public est ouvert sous l'angle de l'art. 83 let. f LTF.
1.4 L'arrêt attaqué, qui déclare irrecevable le recours formé par la Société à l'encontre du second tour d'appel d'offres, ne met pas fin à la procédure d'attribution. Il a donc les traits d'une décision incidente, contre laquelle un recours immédiat au Tribunal fédéral n'est possible qu'à certaines conditions bien précises (cf. art. 92 s. LTF). La seule éventualité envisageable dans le cas particulier est que cette décision cause à la recourante un préjudice irréparable au sens de l'art. 93 al. 1 let. a LTF. Le préjudice irréparable est un dommage de nature juridique qui ne peut pas être réparé ultérieurement par un jugement final ou une autre décision favorable au recourant (ATF 134 III 188 consid. 2.1 p. 190; 133 V 645 consid. 2.1 p. 647 et les références).
En l'espèce, par rapport au dossier de candidature remis aux soumissionnaires lors du premier tour de l'appel d'offres, le système de vélos en libre service se présente comme une prestation importante et entièrement nouvelle. Par ailleurs, celle-ci est totalement étrangère au domaine d'activité de la recourante qui en conteste l'inclusion dans le cahier des charges de la concession d'affichage mise en soumission. Or, si l'intéressée ne pouvait pas attaquer immédiatement ce point du cahier des charges, elle serait tenue de préparer et présenter une offre incluant le système litigieux. A défaut, sa soumission risquerait en effet d'être déclarée nulle ou de pas être prise en compte au cas où ses griefs tendant à faire admettre que ledit système ne peut pas être couplé avec une concession devaient finalement être rejetés au terme du recours formé contre la décision (finale) d'adjudication. Dans cette mesure, la clause contestée du cahier des charges doit pouvoir être entreprise dès à présent par la recourante, car elle est susceptible de lui causer un préjudice irréparable au sens de l'art. 93 al. 1 let. a LTF.
1.5 Pour le surplus, la recourante a qualité pour recourir au sens de l'art. 89 al. 1 LTF, étant directement touchée par la décision attaquée et ayant un intérêt digne de protection à en obtenir l'annulation ou la modification. Déposé en temps utile (cf. art. 100 al. 1 LTF en relation avec les art. 44 et 45 LTF) et dans les formes prescrites par la loi (art. 42 LTF), son recours est donc recevable.
2. Invoquant l'art. 29 al. 2 Cst., la recourante soutient que le Tribunal administratif a insuffisamment motivé son arrêt.
2.1 Le droit d'être entendu implique notamment pour l'autorité l'obligation de motiver sa décision. Il ne lui impose cependant pas d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties; l'autorité peut, au contraire, se limiter à ceux qui, sans arbitraire, lui paraissent pertinents (ATF 133 III 439 consid. 3.3 p. 445; 130 II 530 consid. 4.3 p. 540). Savoir si la motivation présentée est convaincante est une question distincte de celle du droit à une décision motivée. Dès lors que l'on peut discerner les motifs qui ont guidé la décision des juges, le droit à une décision motivée est respecté même si la motivation présentée est erronée (arrêt 4P.308/2005 du 1er juin 2006, consid. 3.2).
2.2 La recourante reproche au Tribunal administratif de n'avoir pas pris la peine d'examiner si, comme elle le faisait valoir en procédure cantonale, le cahier des charges remis aux candidats lors du second tour de l'appel d'offres avait modifié de manière importante les conditions du marché, au point que la procédure devait désormais suivre les règles applicables aux marchés publics. Il est exact que les premiers juges n'ont pas procédé à un tel examen de la situation. Ils ont en effet considéré que les procédures tendant, comme en l'espèce, à l'octroi d'une concession d'affichage, échappaient de manière générale et sans exception possible aux règles des marchés publics. Ils ont motivé leur point de vue en renvoyant à leur arrêt du 19 décembre 2006 rendu lors du premier tour de l'appel d'offres, ainsi qu'à l'ATF 125 I 209 et à deux avis de doctrine. Une telle motivation est suffisante en regard de l'art. 29 al. 2 Cst. Du reste, les critiques de la recourante démontrent qu'elle a parfaitement saisi la position du Tribunal administratif. Quant à savoir si les juges auraient dû examiner si les modifications introduites dans le cadre du second tour de l'appel d'offres changeaient la nature du marché, il s'agit d'une question qui relève du droit.
3. La recourante fait également grief au Tribunal administratif de n'avoir pas constaté les faits qu'elle avait allégués en procédure cantonale en vue d'établir que la procédure litigieuse devait être soumise au droit des marchés publics. Elle y voit une violation de l'art. 97 al. 1 LTF ainsi qu'une application arbitraire (art. 9 Cst.) de l'article 19 de la loi genevoise du 12 septembre 1985 sur la procédure administrative (RS/GE E 5 10) qui prévoit le principe de la maxime d'office en matière d'établissement des faits.
Dès l'instant où, comme on l'a vu, les premiers juges ont estimé que les règles en matière de marchés publics étaient de manière générale inapplicables à toute procédure concernant l'attribution d'une concession, ils pouvaient, sans arbitraire ni violation de la maxime d'office, ne pas tenir compte des allégués exposés par la recourante en vue de démontrer que le marché en cause faisait figure d'exception en raison de la nature particulière des prestations litigieuses. Dans cette mesure, comme le grief lié au droit d'être entendu, les critiques concernant la constatation des faits reviennent, en réalité, à contester l'appréciation juridique contenue dans l'arrêt attaqué.
4. Pour déterminer si le Tribunal administratif devait entrer en matière sur le recours, il faut se demander si les règles propres aux marchés publics sont applicables.
4.1 Aux termes de l'art. 2 al. 7 LMI, la transmission de l'exploitation d'un monopole cantonal ou communal à des entreprises privées doit faire l'objet d'un appel d'offres et ne peut discriminer des personnes ayant leur établissement ou leur siège en Suisse.
Il est douteux que cette disposition, entrée en vigueur le 1er juillet 2006, quelques jours après la publication de l'appel d'offres litigieux, soit applicable au présent cas. Par ailleurs, son champ d'application et sa portée ne sont pas clairs et soulèvent de nombreuses questions. En particulier, il semble que la procédure d'appel d'offres à laquelle l'art. 2 al. 7 LMI fait référence n'ait pas pour conséquence de subordonner l'octroi des concessions de monopole cantonal ou communal à l'ensemble de la réglementation applicable en matière de marchés publics et que ne sont visées par cette disposition que certaines garanties procédurales minimales, comme celles énoncées à l'art. 9 al. 1 et 2 LMI concernant les voies de droit (cf. Denis Esseiva, Mise en concurrence de l'octroi de concessions cantonales et communales selon l'article 2 al. 7 LMI, in DC 2006, p. 203 ss; Alexander Rey/Benjamin Wittwer, Die Ausschreibungspflicht bei der Übertragung von Monopolen nach revidiertem Binnenmarktgesetz: unter besonderer Berücksichtigung des Elektrizitätsbereichs, in PJA 2007, p. 585 ss; Stefan Rechsteiner/Michael Waldner, Netzgebietszuteilung und Konzessionsverträge für die Elektrizitätsverordnung: aktuelle Fragen und kommende gesetzliche Vorgaben, in PJA 2007, p. 1288 ss, spécial. p. 1295 ss).
Ces questions peuvent rester indécises. En effet, comme on le verra ci-après, les règles de procédure sur les marchés publics doivent, en l'espèce, s'appliquer directement en raison de la nature même du marché en cause, ce qui, en vertu du principe lex specialis derogat generali, exclut l'application concurrente des dispositions de la loi sur le marché intérieur (cf. Esseiva, op. cit., p. 206).
4.2 Dans l'arrêt publié à l'ATF 125 I 209, le Tribunal fédéral a jugé que l'octroi du monopole d'affichage publicitaire sur le domaine public ne relevait pas du droit des marchés publics. Il a tout d'abord relevé qu'une telle concession n'entrait pas dans la notion de marché public, par laquelle on entendait communément l'ensemble des contrats relevant du droit privé passés par les pouvoirs publics avec des soumissionnaires (privés) portant sur l'acquisition de fournitures de constructions ou de services (consid. 6b p. 212). Cet arrêt retient ensuite qu'en accordant le monopole d'affichage publicitaire litigieux sur leur domaine public respectif, les autorités concédantes concernées (soit la Ville et le Canton de Genève) n'intervenaient pas comme "demandeurs" ou "acquéreurs" de prestations, mais se trouvaient bien plutôt dans la position "d'offreurs" ou de "vendeurs", dans la mesure où elles n'entendaient pas acquérir des prestations de services, mais au contraire "vendre" le droit d'utiliser le domaine public à des fins commerciales moyennant une redevance et diverses prestations annexes (consid. 6b p. 213). Concernant ces dernières, il ressort de l'ATF 125 I 209 que le concessionnaire s'engageait à exécuter en faveur des autorités concédantes certaines prestations susceptibles de relever des marchés publics, comme l'élaboration d'un concept d'affichage et de mobilier, l'installation et l'entretien d'éléments de mobilier urbain, ainsi que certaines prestations d'affichage en faveur de la collectivité. Le Tribunal fédéral a toutefois estimé que l'ensemble de ces prestations échappaient aux règles sur les marchés publics, car elles étaient "accessoires" au monopole d'affichage et permettaient à la société concessionnaire d'exercer son activité commerciale à ses risques et profits (consid. 6b p. 215).
4.2 Dans l'arrêt publié à l'ATF 125 I 209, le Tribunal fédéral a jugé que l'octroi du monopole d'affichage publicitaire sur le domaine public ne relevait pas du droit des marchés publics. Il a tout d'abord relevé qu'une telle concession n'entrait pas dans la notion de marché public, par laquelle on entendait communément l'ensemble des contrats relevant du droit privé passés par les pouvoirs publics avec des soumissionnaires (privés) portant sur l'acquisition de fournitures de constructions ou de services (consid. 6b p. 212). Cet arrêt retient ensuite qu'en accordant le monopole d'affichage publicitaire litigieux sur leur domaine public respectif, les autorités concédantes concernées (soit la Ville et le Canton de Genève) n'intervenaient pas comme "demandeurs" ou "acquéreurs" de prestations, mais se trouvaient bien plutôt dans la position "d'offreurs" ou de "vendeurs", dans la mesure où elles n'entendaient pas acquérir des prestations de services, mais au contraire "vendre" le droit d'utiliser le domaine public à des fins commerciales moyennant une redevance et diverses prestations annexes (consid. 6b p. 213). Concernant ces dernières, il ressort de l'ATF 125 I 209 que le concessionnaire s'engageait à exécuter en faveur des autorités concédantes certaines prestations susceptibles de relever des marchés publics, comme l'élaboration d'un concept d'affichage et de mobilier, l'installation et l'entretien d'éléments de mobilier urbain, ainsi que certaines prestations d'affichage en faveur de la collectivité. Le Tribunal fédéral a toutefois estimé que l'ensemble de ces prestations échappaient aux règles sur les marchés publics, car elles étaient "accessoires" au monopole d'affichage et permettaient à la société concessionnaire d'exercer son activité commerciale à ses risques et profits (consid. 6b p. 215).
4.3 Cette jurisprudence a été abondamment commentée en doctrine.
4.3.1 D'une manière générale, les critiques se concentrent sur le fait que l'ATF 125 I 209 définit la notion de marchés public d'une manière trop rigide et schématique qui suffit pour aborder des cas simples (soit des marchés publics que l'on pourrait qualifier de "classiques"), mais qui ne permet en revanche qu'imparfaitement d'appréhender des situations plus complexes rencontrées dans la réalité économique (cf. François Bellanger, La notion de "marché public", une définition sans concession ?, in Les droits de l'homme et la constitution, Etudes en l'honneur du Professeur Giorgio Malinverni, éd. par Andreas Auer/Alexandre Flückiger/Michel Hottelier, Zurich 2008, p. 399 ss, spécial. p. 404; Martin Beyeler, Der objektive Geltungsbereich des Vergaberechts, in Marchés publics 2008, éd. par Jean-Baptiste Zufferey/Hubert Stöckli, Zurich 2008, p. 65 ss, n. 54 ss et 63 ss).
Certains auteurs proposent dès lors de réexaminer la notion de marché public et, en particulier, d'assouplir certaines des conditions qui servent à sa définition. En particulier, une large part de la doctrine est d'avis que l'absence de versement d'une somme d'argent par l'Etat ne doit pas nécessairement conduire à exclure l'existence d'un marché public. Il suffit que la prestation considérée revête un caractère onéreux, mais son paiement doit pouvoir se faire sous n'importe quelle forme, y compris en nature, afin de respecter la flexibilité souhaitée en la matière par l'art. II ch. 2 de l'Accord du 15 avril 1994 sur les marchés publics, entré en vigueur pour la Suisse le 1er janvier 1996 (RS 0.632.231.422; AMP) (cf. Beyeler, op. cit., n. 84 ss et 94; Bellanger, op. cit., p. 401; François Bellanger/Christian Bovet, Marché de l'affichage public ou marché public de l'affichage ?, in DC 1/99, p. 164 s.; Daniel Kunz, Verfahren und Rechtschutz bei der Vergabe von Konzessionen, thèse Berne 2004, p. 167 ss, p. 178 s.; Aurélia Rappo, Les marchés publics: champ d'application et qualification, in RDAF 2005 I p. 165 ss, p. 171; Jean-Baptiste Zufferey/Julien Le Fort, L'assujettissement des PPP au droit des marchés publics, in DC 2/2006, p. 99 ss, p. 101 s.; Jean-Baptiste Zufferey, Le champ d'application du droit des marchés publics - Mise en garde pour tous ceux qui projettent d'y échapper, in Mélanges en l'honneur de Pierre Tercier, Zurich 2008, p. 691 ss, p. 699). Dans le contexte particulier d'une concession, seule une appréciation de l'ensemble des rapports économiques entre l'autorité concédante et le concessionnaire permet, selon Beyeler (op. cit., n. 94), de déterminer si une prestation déterminée est ou non onéreuse. Une partie de la doctrine préconise également, toujours dans l'idée d'assouplir la notion de marché public, de ne subordonner la définition de celle-ci ni à l'existence d'un rapport contractuel nécessairement fondé sur le droit privé (cf. Beyeler, op. cit., n. 69 ss et 72 s.), ni à l'exigence que le pouvoir adjudicateur soit nécessairement le destinataire direct de la prestation (par opposition à l'usager final cf. Beyeler, op. cit., n. 67; Denis Esseiva, Marchés publics/Jurisprudence, in DC 4/2004, p. 165; contra: Kunz, op. cit., p. 172 ss; Jacques Fournier, Vers un nouveau droit des concessions hydroélectriques, thèse Fribourg 2002, p. 271).
4.3.2 La doctrine a également exprimé des critiques sur l'ATF 125 I 209 concernant le rapport entre les notions de concession et de marchés publics.
Selon une minorité d'auteurs, la solution à laquelle aboutit cette jurisprudence serait erronée dans son principe. Ils estiment en effet que l'octroi d'une concession est un acte mixte qui revêt sous certains aspects un caractère contractuel. Dans la mesure où un tel acte vise à décharger la collectivité d'une tâche publique en confiant l'exécution de celle-ci à un particulier, il en découlerait entre l'autorité concédante et le concessionnaire un rapport d'échange tombant sous le régime des marchés publics. La collectivité publique obtient en effet, d'après cette conception, une prestation sous la forme de l'accomplissement d'une tâche publique par un concessionnaire. Or, ce dernier se trouverait, à l'instar de n'importe quel soumissionnaire, dans un rapport de concurrence avec d'autres entreprises, sa rétribution consistant, même si aucune rémunération n'est prévue, en la valeur du monopole qui lui est concédé (cf. Bellanger/Bovet, op. cit., p. 164 ss; Rappo, op. cit., p. 170 s.).
En revanche, la doctrine majoritaire admet, dans la ligne de l'ATF 125 I 209, que les concessions qui ne comportent pas la délégation d'une tâche publique (concessions d'usage du domaine public ou de monopole) échappent au droit des marchés publics, car la collectivité publique, au travers d'une telle opération, n'acquiert pas de manière onéreuse une prestation utile à l'accomplissement de ses tâches publiques, mais ne fait que vendre un droit (cf. Peter Galli/André Moser/Elisabeth Lang/Evelyne Clerc, Praxis des öffentlichen Beschaffungsrecht: eine systematische Darstellung der Rechtsprechung des Bundes, der Kantone und der Europäischen Union, 2ème éd., Zurich/Bâle/Genève 2007, p. 45 ss; Marco Fetz, Öffentliches Beschaffungsrecht des Bundes, in Allgemeines Aussenwirtschafts- und Binnenmartkrecht, éd. par Thomas Cottier/Matthias Oesch, 2ème éd., Bâle 2007, p. 508 ss; Jacques Dubey, Marchés publics/Jurisprudence, in DC 4/2007, p. 192 s.; Denis Esseiva, op. cit., p. 185 et p. 205 s.; du même auteur, Les grandes nouveautés: La législation et les normes privées, in Marchés publics 2008, éd. par Jean-Baptiste Zufferey/Hubert Stöckli, Zurich 2008, p. 1 ss, n. 28 s.; Fournier, op. cit., p. 271; Kunz, op. cit., p. 169 et 175 ss; Etienne Poltier, Les marchés publics: premières expériences vaudoises, in RDAF 2000 I p. 297 ss, p. 310 ss; Claudia Schneider Heusi/Felix Jost, Public Private Partnership - wenn Staat und Private kooperieren, in DR 2006, cahier spécial, p. 27 ss; Yves Donzallaz, Commentaire de la loi sur le Tribunal fédéral, Berne 2008, n. 2831; Bellanger, op. cit., p. 404 s. et 416).
Cependant, plusieurs auteurs soulignent que des problèmes d'interprétation et de qualification peuvent malgré tout se présenter lorsque, en contrepartie de l'octroi d'une concession de monopole, le concessionnaire est appelé à fournir des (contre-)prestations qui, prises isolément, pourraient pour certaines d'entre elles faire l'objet d'un marché public (cf. Bellanger, op. cit., p. 406; Jean-Baptiste Zufferey, Marchés publics/Jurisprudence, in DC 4/99, p. 142; Kunz, op. cit., p. 178 s.; Rappo, op. cit., p. 168; Christian Bovet, Marchés publics/Jurisprudence, in DC 2/2001 p. 59). Une partie de la doctrine préconise dans une telle situation d'assujettir le contrat dans son ensemble à la prestation prépondérante (en règle générale en termes quantitatifs), en s'inspirant de la solution appliquée en droit communautaire (cf. Zufferey, in DC 4/99, p. 142; Rappo, op. cit., p. 173). Bellanger (op. cit., p. 406 ss) propose de n'appliquer le critère de la prestation prépondérante que pour les prestations qui ne sont pas dissociables les unes des autres, tandis que les prestations dissociables devraient être examinées de manière indépendante et seraient chacune d'entre elles susceptibles de faire l'objet d'un marché public si les conditions en sont réunies.
4.4 De ce survol de la doctrine, il ressort que de nombreuses questions demeurent controversées sur les liens entre les notions de marchés publics et de concessions. L'évolution de la pratique, pour sa part, laisse de moins en moins souvent la place à ce qu'il est convenu d'appeler des marchés publics ou des concessions classiques, au profit de rapports juridiques et économiques complexes où une multitude de cas de figure sont envisageables. La solution à adopter dans un cas d'espèce ne peut donc prétendre résoudre l'ensemble de ces questions. Il se dégage néanmoins des critiques de la doctrine et de l'évolution de la pratique que l'ATF 125 I 209 doit être précisé, afin d'éviter que des biens et des services qui, au vu de leur nature, ne devraient normalement être acquis par les collectivités publiques que dans le respect des règles sur les marchés publics, n'échappent aux garanties procédurales propres à cette matière, en raison de l'application stricte d'une règle faisant primer la concession. En d'autres termes, il ne faut pas qu'une collectivité publique puisse, par le biais de l'octroi d'une concession, détourner l'application des règles sur les marchés publics. On peut admettre que tel est notamment le cas lorsque la collectivité subordonne l'octroi d'une concession à des contre-prestations d'une certaine importance qui entrent clairement dans la notion de marché public et sont dissociables de la concession. Dans un tel cas, il se justifie de soumettre l'acquisition de telles prestations aux garanties procédurales propres au droit des marchés publics.
5. En l'espèce, les exigences figurant dans le second tour de l'appel d'offres portant sur la mise à disposition de vélos en libre service entraîneraient, selon la recourante, l'application des règles sur les marchés publics à l'ensemble de l'appel d'offres ou, subsidiairement, aux seules prestations requises en relation avec le système de vélos.
5.1 Ces prestations sont exigées dans le cadre de l'octroi d'une concession d'affichage public, similaire à celle qui était en cause dans l'ATF 125 I 209. Prises isolément, les prestations liées à l'affichage public en tant que telles ne relèvent pas du droit des marchés publics. En octroyant ladite concession, la Ville de Genève n'acquiert en effet aucunement à titre onéreux des moyens utiles à l'accomplissement de ses tâches publiques ni ne vise d'ailleurs véritablement la poursuite d'un intérêt public. Elle ne fait que concéder un monopole d'utilisation du domaine public en échange d'une redevance et de certaines prestations annexes que le concessionnaire s'engage à lui fournir. Conformément à la jurisprudence publiée à l'ATF 125 I 209 et à la doctrine majoritaire (cf. supra consid. 4.3.2), l'octroi de ladite concession, en tant qu'elle porte sur l'affichage public, échappe aux exigences issues des marchés publics, sous réserve des conséquences à tirer de l'éventuelle application de l'art. 2 al. 7 LMI (cf. supra consid. 4.1).
5.2 Il reste à examiner ce qu'il en est des prestations contestées liées à la mise en place d'un système de vélos en libre service et qui, selon la recourante, devraient être soumises au droit des marchés publics.
5.2.1 Le cahier des charges (annexe 5, descriptif concernant le système de vélos en libre service) prévoit que le concessionnaire doit, pendant la durée de la concession (soit cinq ans), supporter tous les coûts relatifs à la mise en place et au fonctionnement du système de vélos en libre service. Ceux-ci comprennent en particulier la remise à la Ville de 500 vélos en prêt, la remise en propriété de 40 stations automatisées où seront stationnés les vélos destinés aux usagers, l'entretien, la réparation et le remplacement des vélos ainsi que les frais d'exploitation comprenant notamment les charges salariales. A cet égard, les vélos doivent pouvoir être pris et rendus dans chacune des stations dont le fonctionnement sera automatisé ou assuré par du personnel. Le concessionnaire doit faire en sorte que les vélos soient "accessibles à la plus large part de la population, tant du point de vue financier que des facilités d'usage et aspects pratiques". Il doit également veiller à ce que les vélos soient toujours correctement répartis entre les différentes stations, afin d'assurer en permanence leur disponibilité pour les usagers sur l'ensemble de la Ville. Ce rééquilibrage doit se faire au moyen de véhicules "peu ou pas polluants". Enfin, le concessionnaire est tenu d'encaisser auprès des usagers une contribution fixée par la Ville, qui doit être rétrocédée à celle-ci "en intégralité".
5.2.2 Ces éléments font apparaître que le système de vélos en libre service représente pour l'autorité concédante un moyen de réaliser une tâche publique. Cette prestation vise en effet à promouvoir la mobilité douce en ville afin, notamment, de limiter les nuisances liées au trafic motorisé. Or, la notion de tâche publique doit être définie largement et englobe toutes les activités qui favorisent un intérêt public, sans être nécessairement elles-mêmes des tâches publiques à proprement parler (cf. Zufferey/Le Fort, op. cit., p. 100; dans le même sens, Beyeler, op. cit., n. 90). Par ailleurs, l'acquisition de cette prestation a un coût pour la Ville. Certes, cette dernière ne s'engage-t-elle pas à payer un montant en espèces en échange du système litigieux de vélos en libre service. Ce point ne suffit toutefois pas à exclure l'existence d'un marché public, contrairement à ce que pourrait laisser penser une lecture littérale de l'ATF 125 I 209 (consid. 6b, p. 214). Comme le soulignent à raison de nombreux auteurs (cf. supra 4.3.1), le paiement d'une prestation soumise au droit des marchés publics peut en effet se faire autrement que par le seul versement d'un prix. Toutes les formes de rémunération sont possibles en vertu de l'art. II par. 2 de l'Accord du 15 avril 1994 sur les marchés publics qui sert de cadre pour l'application de la réglementation en matière de marchés publics (sur l'importance de cet accord pour l'interprétation du droit interne; cf. ATF 134 II 192 consid. 2.3 p. 199; Bellanger, op. cit., p. 400; Olivier Rodondi, Le droit cantonal des marchés publics - Les premières expériences, in RDAF 1999 I p. 265 ss, p. 269). Or, en l'espèce, le montant de la redevance que les soumissionnaires sont prêts à payer pour l'acquisition du monopole d'affichage dépend directement des investissements qu'ils doivent consentir pour respecter les obligations annexes à la concession; leurs offres seront à cet égard d'autant plus basses que les prestations annexes qu'ils devront fournir seront d'un coût élevé; autrement dit, même si la Ville ne verse pas directement une somme d'argent en contrepartie de la prestation litigieuse, celle-ci a bien un prix qui correspond à la diminution du montant offert par les soumissionnaires pour la redevance.
Par ailleurs, les prestations que le concessionnaire doit fournir au titre du système de vélos en libre service font assurément partie des biens et des services visés par l'art. 6 AIMP 1994. Que le concessionnaire conserve la propriété des vélos n'est à cet égard pas déterminant. Les marchés de fournitures englobent en effet les contrats entre un adjudicateur et un soumissionnaire concernant l'acquisition de biens mobiliers, notamment sous forme d'achat, de crédit-bail (leasing), de bail à loyer, de bail à ferme ou de location-vente (art. 6 al. 1 let. b AIMP 1994). Par ailleurs, l'entretien et la réparation des vélos relèvent des marchés de services, de même que les autres prestations liées à l'exploitation et la gestion du système (cf. annexe 4, appendice I de l'Accord GATT [soit l'Accord précité du 15 avril 1994 sur les marchés publics]). Quant aux stations automatisées, il n'est pas exclu qu'elles puissent, selon leur conception, tomber sous le coup des marchés de constructions visés à l'art. 6 al. 1 let. a AIMP 1994.
Enfin, le système de vélos en libre service apparaît parfaitement dissociable de la concession d'affichage. Que le cahier des charges prévoie que le concessionnaire peut utiliser les vélos pour de l'affichage publicitaire et retirer une partie des recettes en découlant apparaît une circonstance marginale impropre à faire admettre que le système litigieux serait dépendant de la concession. Du reste, on ne saurait dire, contrairement à ce qui vaut pour les activités d'affichage en lien avec la concession, que le concessionnaire va exploiter à ses risques et profits le système litigieux. Le cahier des charges lui fixe en effet précisément de nombreuses obligations et ne lui laisse guère d'indépendance pour organiser son activité; en outre, il doit rétrocéder l'ensemble des recettes de location des vélos encaissées auprès des usagers et même une partie des recettes publicitaires induites par l'affichage sur les vélos.
5.2.3 Par conséquent, le système de vélos en libre service tel que décrit dans le cahier des charges comporte toutes les caractéristiques propres à un marché public. En outre, ce système est parfaitement dissociable de l'octroi du monopole d'affichage et ne peut, vu sa nature et son importance, être assimilé à une simple prestation accessoire à la concession. Il n'y a donc pas de raison de soustraire les prestations liées à la mise en place et à l'exploitation du système litigieux aux garanties procédurales propres aux marchés publics.
5.3 Dans ces conditions, le Tribunal administratif devait admettre, en vertu de la protection juridique spécifique prévue pour les marchés publics cantonaux, le droit de la recourante de recourir directement contre les documents d'appel d'offres afférents au système de vélos en libre service sans avoir à attendre la décision d'adjudication, afin de faire constater les éventuelles irrégularités affectant cette phase de la procédure.
6. Il suit de ce qui précède que le recours doit être admis et l'arrêt attaqué annulé, le dossier étant renvoyé au Tribunal administratif (art. 107 al. 2 LTF) pour qu'il entre en matière sur les critiques soulevées par la recourante en relation avec le point du cahier des charges portant sur la fourniture et l'exploitation du système litigieux de vélos en libre service.
Succombant, la Ville de Genève doit supporter les frais de justice (art. 66 al. 4 LTF a contrario; cf. Adrian Hungerbühler, Das Bundesgericht als Rechtsmittelinstanz in Vergabesachen - Auswirkungen der neuen Rechtsmittelordnung, in Marchés publics 2008, éd. par Jean-Baptiste Zufferey/Hubert Stöckli, Zurich 2008, p. 343 ss, n. 53). La recourante, qui obtient gain de cause, a droit à des dépens (art. 68 al. 2 LTF). Avec ce prononcé, la requête d'effet suspensif est sans objet.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt attaqué annulé. Le dossier est renvoyé au Tribunal administratif du canton de Genève pour nouvelle décision au sens des considérants.
2. Les frais judiciaires, arrêtés à 5'000 fr., sont mis à la charge de la Ville de Genève.
3. Une indemnité de 5'000 fr. est allouée à la recourante à titre de dépens, à la charge de la Ville de Genève.
4. Le présent arrêt est communiqué aux mandataires de la recourante et de la Ville de Genève et au Tribunal administratif du canton de Genève.
Lausanne, le 9 janvier 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Le Greffier:
Merkli Addy