Faits:
A. Né en 1980 et ressortissant de la République populaire du Bangladesh, X._ a vu sa demande d'asile rejetée et son renvoi de Suisse prononcé définitivement le 7 janvier 2004. Un délai au 4 mars 2004 lui a été imparti pour quitter la Suisse.
Le 3 février 2004, X._ a indiqué à l'Office cantonal de la population du canton de Genève (ci-après l'Office cantonal) qu'il ne possédait aucun document d'identité du Bangladesh, qu'il refusait d'y retourner et n'entendait entreprendre aucune démarche pour organiser son départ. Il a confirmé cette position les 15 août 2007, 17 janvier, 19 juin, 3 juillet et 21 novembre 2008.
Le 18 novembre 2009, le consulat du Bangladesh a délivré un laisser-passer valable pour trois mois au nom de X._.
Le 25 novembre 2009, le prénommé a été interpellé par la police chargée d'exécuter son renvoi. X._ s'est opposé à son refoulement par un vol de ligne et a été placé en détention administrative pour une durée de trois mois. Cette mise en détention a été confirmée par la Commission cantonale genevoise de recours en matière administrative (ci-après la Commission de recours), mais seulement pour une durée d'un mois, soit jusqu'au 25 décembre 2009.
Le 15 décembre 2009, X._ s'est opposé à son renvoi au Bangladesh prévu par un vol avec escorte policière.
Le 21 décembre 2009, la Commission de recours, donnant suite à la requête de l'Office cantonal, qui entendait organiser le renvoi par vol spécial qui pourrait être mis en place à la fin du mois de février 2010, a prolongé la détention administrative de X._ pour une durée de 3 mois, jusqu'au 25 mars 2010. Le Tribunal administratif du canton de Genève a confirmé cette décision le 7 janvier 2010.
Le 22 février 2010, l'Office fédéral des migrations (ci-après l'Office fédéral) a informé l'Office cantonal que la validité du laisser-passer de X._ avait été prolongée jusqu'au 17 juin 2010 et qu'un vol spécial pour Dhaka était planifié et pourrait avoir lieu à fin mars ou début avril 2010.
B. Le 19 mars 2010, l'Office cantonal a demandé la prolongation de la détention administrative de X._ pour une durée de deux mois.
Le 22 mars 2010, la Commission de recours a entendu les parties. X._ a confirmé qu'il s'opposait à son départ de Suisse et qu'il souhaitait être mis en liberté pour se rendre dans un pays autre que le Bangladesh. La représentante de l'Office cantonal a indiqué, pour sa part, que les vols spéciaux organisés avant que l'Office fédéral ne les suspende à la suite du décès d'une personne renvoyée étaient maintenus. Un tel vol à destination du Bangladesh était prévu dans la deuxième moitié du mois d'avril 2010.
Par décision du 22 mars 2010, la Commission de recours a prolongé la détention administrative de X._ pour une durée de deux mois, soit jusqu'au 25 mai 2010.
Par arrêt du 9 avril 2010, le Tribunal administratif a rejeté le recours interjeté par X._ à l'encontre de la décision du 22 mars 2010. S'agissant de l'organisation d'un vol spécial, les juges cantonaux ont retenu, sur la base des pièces du dossier, que celle-ci était en cours et qu'un tel vol pourrait avoir lieu dans la deuxième moitié du mois d'avril 2010. La détention qui avait débuté le 25 novembre 2009 restait proportionnée, dès lors qu'un vol spécial pourrait être organisé très rapidement, comme l'avait affirmé l'Office des migrations dans des courriers électroniques datés du 19 mars 2010.
C. Contre l'arrêt du 9 avril 2010, X._ forme un recours en matière de droit public au Tribunal fédéral, dans lequel il conclut à l'annulation de l'arrêt attaqué, à ce que sa libération immédiate soit ordonnée, subsidiairement à ce que toutes les mesures utiles à l'établissement des faits pertinents soient mises en oeuvre. Il demande par ailleurs le bénéfice de l'assistance judiciaire.
Le Tribunal administratif n'a pas formulé d'observations, renvoyant à son arrêt. La Commission de recours ne s'est pas prononcée. L'Office cantonal propose de rejeter le recours, soulignant que, selon les informations récentes communiquées par l'Office fédéral, il était probable qu'une reprise des vols spéciaux soit ordonnée d'ici au 31 mai 2010. L'Office fédéral, dans une écriture du 21 mai 2010, a renvoyé, en ce qui concerne la suspension des vols spéciaux, à un mémoire de recours déposé dans une autre procédure pendante devant le Tribunal fédéral, sans produire ce document.
Invité à se déterminer, X._ a maintenu sa position le 27 mai 2010, en produisant un communiqué de presse de l'Office fédéral du 21 mai 2010.

Considérant en droit:
1. 1.1 La voie du recours en matière de droit public (<ref-law>) est en principe ouverte à l'encontre des décisions cantonales en matière de mesures de contrainte (<ref-ruling> consid. 2). Dirigé contre un arrêt rendu en cette matière par une autorité judiciaire cantonale supérieure de dernière instance (cf. art. 86 al. 1 lettre d et al. 2 LTF), le présent recours a été déposé dans le délai prévu par la loi (cf. <ref-law>) et dans les formes requises (<ref-law>).
1.2 La qualité pour recourir au sens de l'<ref-law> suppose notamment que le recourant ait un intérêt actuel digne de protection à l'annulation ou à la modification de la décision entreprise (cf. <ref-ruling> consid. 1.2 p. 365). Cet intérêt actuel doit exister non seulement au moment du dépôt du recours, mais encore au moment où l'arrêt est rendu. Le Tribunal fédéral fait exceptionnellement abstraction de l'exigence d'un intérêt actuel, lorsque la contestation peut se reproduire en tout temps dans des circonstances identiques ou analogues, que sa nature ne permet pas de la trancher avant qu'elle ne perde son actualité et que, en raison de sa portée de principe, il existe un intérêt public suffisamment important à la solution de la question litigieuse (<ref-ruling> consid. 1.1; <ref-ruling> consid. 1.1 p. 81).
En l'espèce, la prolongation litigieuse, prononcée le 22 mars 2010, est arrivée à échéance le 25 mai 2010. Le recourant se trouve toujours en détention, mais sur la base d'une nouvelle décision de la Commission de recours qui, le 20 mai 2010, a prolongé sa détention d'un mois jusqu'au 24 juin 2010. Cette nouvelle décision constitue le seul titre qui justifie actuellement la détention du recourant. Celui-ci n'a donc plus d'intérêt actuel à s'en prendre à l'arrêt attaqué, qui confirme la détention prononcée jusqu'au 25 mai 2010 (cf. arrêt 2C_10/2009 du 5 février 2009 consid. 2 non publié aux <ref-ruling>). Toutefois, les circonstances justifiant de renoncer exceptionnellement à l'intérêt actuel sont remplies en l'espèce. En effet, le litige a trait à l'évaluation de la possibilité de procéder au renvoi du recourant en relation avec la décision de l'Office fédéral de suspendre les vols spéciaux. Or, tant que ces vols n'ont pas repris, la même situation peut se reproduire en tout temps; en outre, plus la durée de la prolongation de la détention est réduite, plus il est difficile, voire impossible selon les voies de recours prévues sur le plan cantonal, que le Tribunal fédéral se prononce avant que la question perde de son actualité. Enfin, s'agissant d'une cause générale, opposable à tous les cas de détention en vue de renvoi, elle revêt un intérêt public.
2. Le recourant a été mis en détention le 25 novembre 2009 et la demande de prolongation litigieuse date du 19 mars 2010. Partant, la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20) est applicable (cf. art. 126 al. 1 LEtr).
3. Il découle de l'art. 76 al. 1 lettre b ch. 3 et 4 LEtr que, lorsqu'une décision de renvoi a été notifiée, l'autorité compétente peut, afin d'en assurer l'exécution, mettre en détention la personne concernée si des éléments concrets font craindre que celle-ci entende se soustraire au renvoi, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer, ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités.
En l'espèce, il ressort des constatations cantonales que le recourant remplit les conditions pour une mise en détention en application de l'art. 76 al. 1 lettre b ch. 3 et 4 LEtr (cf. arrêt 2C_756/2009 du 15 décembre 2009 consid. 2.3.1), ce qui n'est du reste pas contesté. Reste le point de savoir si les conditions pour que la détention se prolonge sont réunies.
4. Selon l'art. 76 al. 3 1ère phrase LEtr, la durée de la détention visée notamment à l'al. 1 lettre b ch. 3 et 4 ne peut excéder trois mois; si des obstacles particuliers s'opposent à l'exécution du renvoi ou de l'expulsion, la détention peut, avec l'accord de l'autorité judiciaire cantonale, être prolongée de quinze mois au plus. S'il s'avère en particulier que l'exécution du renvoi ou de l'expulsion est impossible pour des raisons juridiques ou matérielles, la détention doit être levée (cf. art. 80 al. 6 lettre a LEtr), respectivement la prolongation refusée. Ces raisons doivent être importantes ("triftige Gründe"; ANDREAS ZÜND, Migrationsrecht, 2e éd., 2009, no 8 ad art. 80 LEtr; THOMAS HUGI, Zwangsmassnahmen im Ausländerrecht, in Ausländerrecht, 2009, no 10.111 p. 476). Ainsi, l'exécution du renvoi doit être qualifiée d'impossible lorsque le rapatriement est pratiquement exclu, même si l'identité et la nationalité de l'étranger sont connues et que les papiers voulus peuvent être obtenus. Tel est par exemple le cas si le déplacement de la personne concernée n'est pas concevable pour des raisons de santé ou qu'un Etat refuse de reprendre certains de ses ressortissants (cf. <ref-ruling> consid. 2 p. 220). Il ne suffit pas que l'exécution du renvoi soit momentanément impossible (par exemple faute de papiers d'identité), tout en restant envisageable dans un délai prévisible (cf. ZÜND, op. cit., no 1 ad art. 76 LEtr; arrêt 2C_256/2008 du 4 avril 2008 consid. 7.1). En tous les cas, la durée de la détention, envisagée dans son ensemble, doit apparaître proportionnée (<ref-ruling> consid. 2.2 p. 100; <ref-ruling> consid. 1 p. 58).
5. Le recourant dénonce l'arbitraire dans l'établissement des faits, en reprochant au Tribunal administratif d'avoir retenu que le vol spécial destiné à le rapatrier pourrait être organisé très rapidement et d'avoir ainsi méconnu la décision de suspendre les vols spéciaux prise par l'Office fédéral.
5.1 L'arbitraire recouvre l'inexactitude manifeste au sens de l'art. 97 al. 1 et 105 al. 2 LTF (cf. <ref-ruling> consid. 1.4.3 p. 254 s.). Selon la jurisprudence, l'appréciation des preuves ou l'établissement des faits sont arbitraires lorsque l'autorité n'a manifestement pas compris le sens et la portée d'un moyen de preuve, si elle ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision ou lorsqu'elle tire des constatations insoutenables des éléments recueillis (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2a p. 41). Pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que la motivation formulée soit insoutenable, il faut encore que la décision apparaisse arbitraire dans son résultat (<ref-ruling> consid. 1.3 p. 4 s.; <ref-ruling> consid. 3.1 p. 265 s.).
5.2 En l'espèce, il ressort de l'arrêt attaqué que le Tribunal administratif a considéré, au regard des pièces figurant au dossier, que l'organisation d'un vol spécial à destination du Bangladesh était toujours en cours et que le renvoi du recourant pourrait avoir lieu dans la deuxième moitié du mois d'avril 2010. La seule pièce allant en ce sens est une déclaration de la représentante de l'Office cantonal du 22 mars 2010, selon laquelle les vols organisés avant la suspension par l'Office fédéral restaient maintenus. Celle-ci n'a produit aucun document écrit pour confirmer ses dires, mais s'est référée à une source indirecte, soit des indications que l'Office fédéral aurait transmises à l'Office cantonal qui lui en avait fait part. Or, aucun élément ne confirme ces dires. Au contraire, comme le relève le recourant, il ressort du communiqué de presse de l'Office fédéral daté du 18 mars 2010 qu'à la suite du décès d'une personne détenue, il a été décidé "de ne plus effectuer de vols spéciaux tant que ce cas n'est pas élucidé". L'arrêt attaqué reproduit une déclaration de l'Office fédéral du 19 mars 2010, selon laquelle la suspension des vols spéciaux serait bientôt levée, ce qui signifie qu'avant cette reprise, le recourant ne pourra être rapatrié.
En pareilles circonstances, l'arrêt attaqué rendu le 9 avril 2010, lorsqu'il constate que l'organisation d'un vol spécial à destination du Bangladesh est toujours en cours et que le renvoi du recourant pourrait avoir lieu dans la deuxième moitié du mois d'avril 2010, est manifestement inexact. Les juges devaient au contraire tenir compte du fait que la décision de l'Office fédéral de suspendre les vols spéciaux depuis le 18 mars 2010 s'appliquait aussi au vol du recourant. Encore faut-il se demander, sous l'angle de l'arbitraire, si l'omission de cet élément est de nature à modifier le résultat de la décision entreprise.
5.3 La suspension des vols spéciaux à partir du 18 mars 2010 a rendu l'exécution du renvoi du recourant impossible. Tant que l'Office fédéral ne revient pas sur sa décision, le rapatriement est exclu en pratique, peu importe que le recourant dispose d'un laisser-passer. Cette impossibilité est certes en principe momentanée. Cela ne signifie pas pour autant qu'elle échappe de ce fait à l'art. 80 al. 6 lettre a LEtr, à moins que l'exécution du renvoi apparaisse envisageable dans un délai prévisible (cf. supra consid. 4). Pour le déterminer, on ne peut que se fonder sur les explications fournies par l'Office fédéral quant à son intention de reprendre les vols spéciaux, étant précisé que, s'agissant de savoir si le renvoi est ou non envisageable dans un délai prévisible, de simples déclarations d'intention ne sont pas suffisantes.
5.4 L'arrêt attaqué ne contient aucune indication précise et concrète sur la reprise des vols spéciaux par l'Office fédéral. La déclaration de celui-ci du 19 mars 2010 reproduite dans l'arrêt attaqué selon laquelle "nous partons du principe que l'enquête en cours par rapport à l'incident récent sera terminée le plus vite possible et que la suspension des vols spéciaux sera bientôt levée" n'est pas suffisante, car elle ne fait état que de suppositions.
Invité à se prononcer, l'Office fédéral n'a fourni, dans ses observations du 21 mai 2010 au Tribunal fédéral, aucune information précise à ce sujet, en se contentant de renvoyer à un recours déposé le 6 mai 2010 dans une autre affaire pendante devant la Cour de céans, sans même produire ce document. Ce procédé est inadmissible en tout cas lorsque, comme en l'espèce, le document auquel il est renvoyé n'est pas joint à la détermination (cf. arrêt 9C_47/2008 du 29 septembre 2008 consid. 2.2). En outre, le respect des garanties de procédure exige que les observations puissent être transmises aux parties. Or, il n'est pas question de remettre à un recourant un mémoire concernant une procédure relative à un tiers. Au demeurant, dans cet acte, l'Office fédéral ne donne aucune information précise, ne faisant état que d'une probable reprise des vols en mai 2010, de sorte que ce document, outre qu'il n'est pas recevable, ne contient pas d'éléments déterminants.
Le recourant, dans ses dernières observations, a également fourni le dernier communiqué de presse de l'Office fédéral, qui date du 21 mai 2010. Il s'agit là d'un élément nouveau qui ne peut être pris en considération (cf. <ref-law>) pour se prononcer sur le bien-fondé de l'arrêt attaqué.
5.5 Il découle de ce qui précède qu'au moment où il a statué, le Tribunal administratif ne disposait d'aucun élément concret permettant de conclure que la suspension des vols spéciaux par l'Office fédéral allait être levée dans un délai pouvant être évalué. Par voie de conséquence, l'exécution du renvoi du recourant était à ce moment-là frappée d'une impossibilité au sens de l'art. 80 al. 6 lettre a LEtr, de sorte que la détention n'aurait pas dû être prolongée.
6. Dans ces circonstances, le recours doit être admis et l'arrêt attaqué annulé. Cette annulation n'a toutefois pas pour effet de lever la détention du recourant, dès lors que la décision entreprise statuait sur le bien-fondé de la prolongation de la détention du recourant ordonnée le 22 mars 2010, qui arrivait à expiration le 25 mai 2010. Cette conséquence provient du fait que la Cour de céans a considéré à titre exceptionnel qu'il pouvait être statué, malgré l'absence d'intérêt actuel au recours (cf. supra consid. 1.2).
La détention du recourant repose actuellement sur la prolongation ordonnée par la Commission de recours le 20 mai 2010 pour une durée d'un mois. Cette décision n'est toutefois justifiée que si ladite Commission, au moment de statuer, était en possession d'éléments suffisamment concrets émanant de l'Office fédéral concernant la reprise des vols spéciaux qui lui permettaient d'en conclure que le renvoi du recourant était envisageable dans un délai prévisible. Il appartient ainsi aux autorités cantonales compétentes de revoir cette question d'office et, en l'absence d'informations précises, de prononcer la levée immédiate de la détention du recourant en application de l'art. 80 al. 6 lettre a LEtr (cf. <ref-ruling> consid. 3c p. 5; arrêt 2C_756/2009 du 15 décembre 2009 consid. 4.1; ZÜND, op. cit., no 7 ad art. 80 LEtr).
A cet égard et par économie de procédure, il convient de préciser que le communiqué de presse du 21 mai 2010, qui mentionne uniquement que l'Office fédéral a décidé que l'organisation des vols spéciaux devrait reprendre progressivement, du fait que les mesures adoptées impliquent des capacités supplémentaires pour être mises en oeuvre, ne constitue pas une déclaration suffisamment précise permettant d'en déduire que le renvoi du recourant pourra être exécuté dans un délai prévisible.
7. Bien qu'il succombe, le canton de Genève n'a pas à supporter de frais judiciaires (cf. <ref-law>); en revanche, il convient de mettre à sa charge les dépens alloués au recourant, qui obtient gain de cause (cf. <ref-law>). Dans ces circonstances, la demande d'assistance judiciaire devient sans objet.
Le Tribunal fédéral ne fera pas usage de la possibilité prévue à l'<ref-law> et renverra la cause au Tribunal administratif pour qu'il statue sur les dépens de la procédure cantonale.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt attaqué annulé dans le sens des considérants.
2. La demande d'assistance judiciaire est sans objet.
3. Il n'est pas perçu de frais.
4. Le canton de Genève versera au recourant une indemnité de 2'000 fr. à titre de dépens.
5. La cause est renvoyée au Tribunal administratif pour qu'il statue sur les dépens de la procédure cantonale.
6. Le présent arrêt est communiqué au mandataire du recourant, à l'Office cantonal de la population, à la Commission cantonale de recours en matière administrative et au Tribunal administratif du canton de Genève, 1ère section, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 1er juin 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Vianin