Faits:
A. X._, ressortissant colombien né en 1960, serait arrivé à Genève à la fin janvier 1994 avec son ex-compagne, Y._, dont il s'était séparé en 1993. Ils avaient eu deux enfants, A._, né en 1989, et B._, né en 1990, tous deux restés en Colombie, où vivait également la fille de X._, née d'une précédente relation.
Le 22 novembre 1996, Y._ a épousé un ressortissant portugais titulaire d'une autorisation d'établissement en Suisse. Mise au bénéfice d'une autorisation de séjour au titre du regroupement familial, elle réside depuis lors à Genève. En décembre 1996, ses enfants A._ et B._ sont arrivés en Suisse après avoir obtenu une autorisation de séjour pour vivre auprès de leur mère et de l'époux de celle-ci.
Par ordonnance de condamnation du 17 octobre 1998, X._ a été reconnu coupable de conduite en état d'ébriété, de violation des règles de la circulation et d'infraction à la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113; en vigueur jusqu'au 31 décembre 2007). Il a été condamné à une peine d'emprisonnement assortie du sursis pendant trois ans. A titre de peine accessoire, une expulsion ferme du territoire suisse pour une durée de cinq ans a été prononcée à son endroit.
Le 17 février 2004, X._ a déposé une demande d'autorisation de séjour au titre du regroupement familial, en invoquant l'art. 8 CEDH.
Le 25 janvier 2005, le prénommé a adressé une nouvelle demande d'autorisation de séjour à l'Office cantonal de la population du canton de Genève. Le même jour, Z._ a déposé une demande d'autorisation de séjour avec activité lucrative en sa faveur.
Le 31 janvier 2005, l'Office cantonal de la population a informé X._ qu'il était disposé à soumettre sa requête à l'Office fédéral des migrations avec un préavis favorable en vue de l'octroi d'une autorisation de séjour fondée sur l'art. 13 lettre f de l'ordonnance fédérale du 6 octobre 1986 limitant le nombre des étrangers (OLE; en vigueur jusqu'au 31 décembre 2007).
Le 30 septembre 2005, l'Office fédéral des migrations a refusé de délivrer une telle autorisation de séjour.
Le 25 octobre 2005, X._ a conclu avec son ex-compagne par-devant le Service de protection de la jeunesse une convention selon laquelle leur fils cadet B._, alors âgé de quinze ans, passerait la semaine auprès de son père et les week-ends chez sa mère.
Le 4 novembre 2005, X._ a recouru au Tribunal administratif fédéral à l'encontre de la décision de l'Office fédéral des migrations. Il a été débouté par arrêt du 25 octobre 2007.
Le 6 mai 2008, l'Office cantonal de la population a refusé d'octroyer au prénommé une autorisation de séjour au titre du regroupement familial et lui a imparti un délai échéant le 31 juillet 2008 pour quitter la Suisse.
X._ a déféré ce prononcé à la Commission cantonale de recours de police des étrangers - devenue entre-temps la Commission cantonale de recours en matière administrative (ci-après: la Commission de recours). Après l'avoir entendu, cette autorité a rejeté le recours par décision du 24 février 2009. Elle a considéré qu'en l'absence d'un lien conjugal avec son ex-compagne, le recourant ne pouvait se prévaloir de l'art. 17 al. 2 LSEE. Quant à l'art. 8 CEDH, il tendait à protéger avant tout les relations entre époux et celles entre parents et enfants mineurs vivant en ménage commun. Or, dans le cas particulier, les deux fils du recourant étaient majeurs. La Commission de recours a en outre relevé qu'un recours contre son prononcé n'aurait pas d'effet suspensif.
Le 14 avril 2009, X._ a recouru à l'encontre de cette décision au Tribunal administratif du canton de Genève. A titre préalable, il a conclu à ce que cette autorité confère l'effet suspensif à son acte. Sur le fond, il a fait valoir notamment que le moment déterminant pour juger de la réalisation des conditions du regroupement familial serait celui du dépôt de la demande, soit en l'occurrence le 17 février 2004. Or, à cette date, aucun de ses deux fils n'avait encore atteint l'âge de la majorité.
B. Par décision du 18 juin 2009, la Présidente du Tribunal administratif a rejeté la demande d'effet suspensif traitée comme une requête de mesures provisionnelles. En effet, s'agissant de conférer l'effet suspensif à un recours dirigé contre une décision (négative) refusant d'octroyer une autorisation de séjour, il faudrait distinguer selon que l'étranger requérant disposait ou non jusque-là d'un titre de séjour en Suisse. C'est seulement dans l'affirmative que le Tribunal administratif pourrait traiter la requête comme une demande de restitution de l'effet suspensif, sous l'angle de l'art. 66 al. 2 de la loi genevoise sur la procédure administrative du 12 septembre 1985 (LPA; RS/GE E 5 10). En revanche, le cas d'un étranger qui, à l'instar du recourant, ne disposait pas jusque-là d'une autorisation de séjour, devrait être examiné à la lumière des règles plus restrictives sur les mesures provisionnelles (art. 21 LPA). En l'occurrence, il n'y aurait pas lieu de permettre au recourant, par la voie de mesures provisionnelles, de demeurer en Suisse jusqu'au prononcé du jugement au fond, car cela reviendrait à préjuger favorablement de l'issue du litige, alors que les conditions d'un regroupement familial ou d'une exception aux mesures de limitation ne sembleraient a priori pas réunies.
C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, en substance, de réformer la décision du 18 juin 2009 en ce sens que son recours du 14 avril 2009 au Tribunal administratif est doté de l'effet suspensif, sous suite de frais et dépens. A titre préalable, il demande que l'effet suspensif soit conféré au présent recours. Il se plaint d'une application arbitraire du droit cantonal.
L'autorité précédente s'en remet à justice quant à la recevabilité du recours et persiste au surplus dans les considérants et le dispositif de sa décision. L'Office de la population renonce à se déterminer.
Par ordonnance présidentielle du 20 juillet 2009, il a été décidé qu'aucune mesure d'exécution de la décision attaquée ne pourrait être prise jusqu'au prononcé sur la requête d'effet suspensif.

Considérant en droit:
1. Le 1er janvier 2008 est entrée en vigueur la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20), qui a remplacé la loi fédérale sur le séjour et l'établissement des étrangers. En vertu de l'art. 126 al. 1 LEtr, les demandes déposées avant l'entrée en vigueur de la loi sont régies par l'ancien droit.
En l'occurrence, la demande d'autorisation de séjour a été déposée le 17 février 2004, puis de nouveau le 25 janvier 2005, soit avant l'entrée en vigueur de la nouvelle loi. La présente affaire doit donc être examinée à la lumière de l'ancienne loi fédérale sur le séjour et l'établissement des étrangers.
2. 2.1 Selon l'art. 83 lettre c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donne droit. Comme les autres clauses d'exclusion de l'<ref-law>, cette disposition vaut pour toutes les décisions rendues dans une affaire tombant sous le coup d'une exception, qu'il s'agisse d'une décision de fond ou de procédure (Alain Wurzburger, Commentaire de la LTF, 2009, no 17 ad <ref-law>).
2.2 Selon la jurisprudence, un étranger peut, selon les circonstances, se prévaloir du droit au respect de sa vie privée et familiale au sens de l'art. 8 § 1 CEDH pour s'opposer à une éventuelle séparation de sa famille. Encore faut-il, pour pouvoir invoquer cette disposition, que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse soit étroite et effective (<ref-ruling> consid. 3.1 p. 285/286, 129 II 193 consid. 5.3.1 p. 211, 215 consid. 4.1 p. 218). Les relations visées par l'art. 8 CEDH sont avant tout celles qui existent entre époux, ainsi que les relations entre parents et enfants mineurs vivant en ménage commun (<ref-ruling> consid. 1d/aa p. 65; <ref-ruling> consid. 1d p. 261). S'agissant d'autres relations entre proches parents, la protection de l'art. 8 CEDH suppose que l'étranger se trouve dans un état de dépendance particulier à l'égard du parent ayant le droit de résider en Suisse. Tel est le cas lorsqu'il a besoin d'une attention et de soins que seuls les proches parents sont en mesure de prodiguer. Cela vaut notamment pour les enfants majeurs vis-à-vis de leurs parents (<ref-ruling> consid. 2 p. 14). Les prétentions tirées de l'art. 8 CEDH sont examinées sur la base de l'état de fait existant lors du prononcé du jugement (<ref-ruling> consid. 2 p. 13/14; arrêt 2A.558/2006 du 22 février 2007 consid. 2.3).
2.3 En l'occurrence, les deux fils du recourant sont entre-temps devenus majeurs. Une relation de dépendance n'étant pas alléguée, le recourant ne peut valablement invoquer l'art. 8 CEDH. Il ne peut pas non plus se prévaloir de l'art. 17 al. 2 LSEE aux fins d'en déduire un droit à une autorisation de séjour. Il s'ensuit que le recours en matière de droit public est irrecevable, en vertu de l'art. 83 lettre c ch. 2 LTF. L'acte du recourant ne peut du reste pas davantage être reçu comme recours constitutionnel subsidiaire. En effet, l'<ref-law> fait dépendre la qualité pour interjeter un tel recours d'un intérêt juridique à l'annulation ou à la modification de la décision attaquée. Selon la jurisprudence, le principe de l'interdiction de l'arbitraire (art. 9 Cst.) ne confère pas à lui seul une position juridiquement protégée au sens de la disposition précitée. Un recourant n'a qualité pour former un recours constitutionnel subsidiaire que si les dispositions légales dont il dénonce l'application arbitraire lui accordent un droit ou servent à protéger ses intérêts prétendument lésés (<ref-ruling> consid. 4.1 p. 191 et 6.3 p. 200 et les arrêts cités).
En l'occurrence, le recourant soutient que le rejet par l'autorité précédente de sa requête d'effet suspensif est arbitraire. En effet, de son point de vue, les conditions dont l'art. 66 al. 2 LPA - qui serait applicable en vertu du renvoi de l'art. 3 al. 3 de la loi genevoise du 16 juin 1988 d'application de la loi fédérale sur les étrangers (LaLEtr; RS/GE F 2 10) - fait dépendre la restitution de l'effet suspensif, seraient réalisées.
Selon l'art. 3 al. 3 LaLEtr, le recours au Tribunal administratif contre la décision de la Commission cantonale de recours en matière administrative n'a pas d'effet suspensif. L'art. 66 al. 2 LPA est toutefois réservé. Aux termes de cette dernière disposition, lorsque aucun intérêt public ou privé prépondérant ne s'y oppose, la juridiction de recours peut, sur la demande de la partie dont les intérêts sont gravement menacés, retirer ou restituer l'effet suspensif.
A supposer que l'art. 66 al. 2 LPA soit applicable - et non l'art. 21 LPA, comme l'a admis l'autorité précédente -, cette disposition ne confère pas au recourant un droit à ce que son recours soit doté de l'effet suspensif. Il s'agit au contraire d'une disposition qui laisse la restitution de l'effet suspensif à l'appréciation de l'autorité de recours, laquelle procède à une pesée des intérêts. Dans ces conditions, le recourant n'a pas qualité pour se plaindre par la voie du recours constitutionnel subsidiaire que le refus de conférer l'effet suspensif à son recours serait arbitraire.
3. Vu ce qui précède, le recours doit être déclaré irrecevable.
Avec la présente décision, la requête d'effet suspensif est sans objet.
Succombant, le recourant supporte les frais judiciaires (cf. <ref-law>) et n'a pas droit à des dépens (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Des frais judiciaires de 1'500 fr. sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, à l'Office cantonal de la population et à la Présidente du Tribunal administratif du canton de Genève, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 10 septembre 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Vianin