Faits: A. X._, né en 1976, originaire du Brésil, séjourne et travaille sans autorisation en Suisse depuis plusieurs années. Le 27 avril 2007, l'Office cantonal de la population a prononcé à l'encontre de l'intéressé une décision de renvoi de Suisse, en application de l'art. 12 de loi fédérale sur le séjour et l'établissement des étrangers du 26 mars 1931 (LSEE; RS 1 113) et lui a imparti un délai au 30 juin 2007 pour quitter le territoire de la Confédération. Le 20 décembre 2007, X._ a été refoulé à destination de Rio de Janeiro par les services de police. B. Le 22 mai 2008, de retour à Genève, l'intéressé a sollicité une autorisation de séjour pour conclure un partenariat enregistré avec Y._. Le 2 décembre 2008, X._ a été interpellé par la police après avoir vendu une dose d'héroïne et déclaré être consommateur d'héroïne. Le 5 décembre 2008, l'Office cantonal de la population a refusé de lui délivrer une autorisation de séjour et lui a imparti un délai au 15 janvier 2009 pour quitter la Suisse. Le 10 mars 2009, l'Office cantonal de la population a chargé la police d'exécuter le renvoi de l'intéressé à destination du Brésil. Le 24 août 2009, le Commissaire de police a ordonné la mise en détention administrative de l'intéressé pour un mois. Le refoulement prévu le 25 août 2009 à destination du Brésil a échoué, l'intéressé s'étant opposé à l'exécution de celui-ci. Le 22 septembre 2009, l'Office fédéral des migrations a prononcé une mesure d'interdiction d'entrée en Suisse à l'encontre de X._, valable jusqu'au 21 septembre 2014, qui lui a été notifiée le 24 septembre 2009. Ayant vécu en France, il a été réadmis par les autorités françaises. Le 17 novembre 2009, il a été interpellé à Genève. Prévenu d'infraction à l'art. 115 de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20), il a été relaxé et refoulé sur la France. Il en a été de même les 2 et 3 décembre 2009. Le 10 mars 2010, il a une nouvelle fois été interpellé par la police genevoise pour une affaire de stupéfiants. Le 11 mars 2010, il a été prévenu d'infractions aux art. 19 de la loi fédérale sur les stupéfiants et les substances psychotropes du 3 octobre 1951 (LStup; RS 812.121) et 115 LEtr, puis condamné par le juge d'instruction le 11 mars 2010 à une peine privative de liberté de trente jours pour ces mêmes infractions. Le 8 avril 2010, il a été libéré et remis à la police. Le même jour, l'Office cantonal de la population a prononcé à son encontre une décision de renvoi de Suisse, exécutoire nonobstant recours, et la police a été chargée d'exécuter sans délai ledit renvoi. C. Le 8 avril 2010, le Commissaire de police a prononcé un ordre de mise en détention administrative à l'encontre de l'intéressé pour trois mois, soit jusqu'au 10 juillet 2010. Par décision du 12 avril 2010, la Commission cantonale de recours en matière administrative a confirmé l'ordre de mise en détention administrative du 8 avril 2010. Le 20 avril 2010, X._, assisté d'un avocat commis d'office, a recouru contre cette décision auprès du Tribunal administratif du canton de Genève en concluant à l'annulation de cette décision et à sa libération immédiate. D. Par arrêt du 30 avril 2010, le Tribunal administratif a rejeté le recours. A l'appui de son arrêt, le Tribunal administratif a jugé que les conditions pour le prononcé d'une mise en détention administrative au sens de l'art. 76 al. 1 let. b ch. 2 et 3 LEtr étaient remplies. Il a aussi jugé que le renvoi était possible. En effet, le traitement à la méthadone n'était pas un traitement nécessaire et vital et aucun certificat médical n'établissait que la cure était suivie de manière sérieuse et régulière, de sorte que rien n'empêchait son interruption tandis que les soins que nécessiterait l'épilepsie n'étaient pas même allégués. L'obtention d'un laissez-passer pour le Brésil devait être rapide puisque l'intéressé y avait déjà été renvoyé et qu'il en détenait la nationalité. En particulier, une reprise des vols spéciaux dans le courant du mois de mai 2010, après leur suspension provisoire le 21 avril 2010, paraissait très réaliste. Le maintien en détention était proportionné à la situation. E. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt rendu le 30 avril 2010 par le Tribunal administratif, la décision rendue le 12 avril 2010 par la Commission de recours en matière administrative ainsi que l'ordre de mise en détention prononcé le 8 avril 2010 et d'ordonner sa libération immédiate. Il se plaint d'arbitraire dans l'application [recte: dans l'établissement] des faits et de la violation de l'art. 80 al. 6 let. a LEtr. Il sollicite l'octroi de l'assistance judiciaire. Le Tribunal administratif se réfère aux considérants de l'arrêt attaqué. L'Etat-major de la police du canton de Genève propose le rejet du recours. L'intéressé a déposé des contre-observations. Bien que dûment invité à déposer des observations sur recours, l'Office fédéral des migrations n'a pris aucune position. 