Faits: A. Arrivé en Suisse le 11 juin 2007, X._, né en 1988, a déposé une demande d'asile comme ressortissant sénégalais. Par décision du 13 juillet 2007, l'Office fédéral des migrations n'est pas entré en matière sur sa requête et a prononcé son renvoi de Suisse. Le 25 juillet 2007, le Tribunal administratif fédéral a rejeté le recours de X._ contre cette décision. Entré dans la clandestinité, X._ a été interpellé le 25 octobre 2007 à Genève et mis à disposition des autorités valaisannes. S'annonçant d'origine gambienne et non sénégalaise, comme déclaré précédemment, il ne disposait d'aucune pièce d'identité et n'avait entrepris aucune démarche afin d'en obtenir. Par décision du 26 octobre 2007, le Service de l'état civil et des étrangers du canton du Valais (ci-après: le Service cantonal) a mis X._ en détention pour une durée maximale de trois mois. Cette décision a été confirmée par l'arrêt du 30 octobre 2007 du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) qui a retenu que l'intéressé avait fait des déclarations quant à sa nationalité et concernant sa famille. Le 22 novembre 2007, X._, muni d'un laissez-passer émis par les autorités gambiennes, valable pour le jour du voyage, a refusé d'embarquer sur un vol à destination de la Gambie. B. A la demande du Service cantonal, le Tribunal cantonal a prolongé la détention de X._ jusqu'au 26 avril 2008 par arrêt du 24 janvier 2008. Il a jugé que l'attitude du recourant qui avait refusé de prendre le vol du 22 novembre 2007 justifiait cette prolongation. En outre, les autorités avaient fait preuve de diligence dans le traitement de l'affaire. Le 25 mars 2008, X._ devait prendre un vol pour Banjul via Francfort. La compagnie aérienne a toutefois refusé, le jour même du départ, de le prendre en charge, une escorte policière n'ayant été prévue que jusqu'à Francfort. C. Le 9 avril 2008, le Service cantonal a requis une nouvelle prolongation de détention de trois mois au Tribunal cantonal. Ledit Tribunal, dans un arrêt du 25 avril 2008, a prolongé jusqu'au 26 juillet 2008 la détention de X._. Il a retenu que l'exigence d'une escorte policière jusqu'à Banjul avait surpris les autorités chargées du rapatriement, la réservation auprès de la compagnie aérienne mentionnant que l'escorte n'était prévue que jusqu'à Francfort. Un vol spécial devait être prévu pour le retour de X._ dans son pays. Le vol du mois de mai était déjà complet. Aucun vol n'était prévu en juin à cause du championnat européen de football. Il fallait attendre juillet, voire le mois d'août, ce qui était indépendant de la volonté et de la sphère d'influence des autorités suisses. X._ persistait en outre à vouloir se rendre ailleurs qu'en Afrique, bien qu'il soit dépourvu de passeport. D. 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 du 25 avril 2008 du Tribunal cantonal et de le libérer. Il invoque le manque de diligence des autorités suisses ainsi que la violation de l'interdiction de l'arbitraire et de son droit d'être entendu. Il requiert l'assistance judiciaire "totale". Le Service cantonal conclut au rejet du recours sous suite de frais. L'Office fédéral des migrations renvoie à la réponse du Service cantonal et conclut, implicitement, au rejet du recours. Le Tribunal cantonal a renoncé à déposer des observations.