A. Né en 1992, X. est de nationalité algérienne.

Le 5 octobre 2010, l'Office fédéral des migrations (ci-après: l'Office fédéral) a ordonné le renvoi de X., refusant d'entrer en matière sur la requête d'asile déposée par celui-ci. Le 22 février 2011, il a rejeté la demande de reconsidération formée par l'intéressé.

X. a été placé en détention administrative par le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) du 19 juin au 19 juillet 2011, date de sa mise en liberté par ladite autorité (art. 105 al. 2 LTF).

Le 19 juillet 2011, il a été placé dans un foyer qu'il a, selon le Service cantonal, quitté sans laisser d'adresse le 27 juillet 2011, ce que conteste X.

En janvier 2012, il a déménagé chez une autre femme que celle qui l'avait accueilli à sa sortie de détention administrative en 2011, reconnaissant ne pas avoir avisé les autorités de ce déménagement.

X. a aussi admis avoir travaillé au noir.

B. Le 15 octobre 2013, le Service cantonal a placé X. en détention pour trois mois au plus. Entendu le 18 octobre 2013 devant le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge unique), X. a refusé de rentrer dans son pays pour rester en Suisse avec sa fille de deux ans et demi et une femme enceinte de lui. Il n'a par ailleurs pas essayé de justifier de manière convaincante les deux dates de naissance différentes qu'il avait données lors d'interrogatoires en Suisse.

Par arrêt du 18 octobre 2013, le Juge unique a approuvé la décision de mise en détention du Service cantonal du 15 octobre 2013. Il a par ailleurs rejeté les demandes de libération et d'assistance judiciaire formées parallèlement par X.

C. A l'encontre de l'arrêt du 18 octobre 2013, X. dépose un recours en matière de droit public au Tribunal fédéral. Il conclut en particulier à l'annulation de l'arrêt attaqué et à sa mise en liberté immédiate.

Le Tribunal fédéral a admis le recours, annulé l'arrêt cantonal attaqué, ordonné la libération immédiate du recourant, auquel il a alloué des dépens, et renvoyé la cause au Tribunal cantonal pour qu'il statue sur les dépens de l'instance cantonale.

(résumé)

5. Le recourant se plaint d'une violation de l'art. 76 LEtr (RS 142. 20).

5.1 La détention administrative porte une atteinte grave à la liberté personnelle et ne peut être ordonnée que dans le respect de l'art. 5 par. 1 let. f CEDH (cf. ATF 135 II 105 consid. 2.2.1 p. 107) et de l'art. 31 Cst., ce qui suppose en premier lieu qu'elle repose sur une base légale. Le respect de la légalité implique ainsi que la mise en détention administrative ne soit prononcée que si les motifs prévus dans la loi sont concrètement réalisés (arrêts 2C_256/2013 du 10 avril 2013 consid. 4.1; 2C_478/2012 du 14 juin 2012 consid. 2.1).

5.2 En outre, selon la jurisprudence, il est certes admissible qu'un étranger, libéré d'une première détention administrative, soit détenu une nouvelle fois en vue de son renvoi dans le cadre de la même procédure; il faut toutefois qu'un changement déterminant des circonstances permette de le justifier (arrêt 2A.428/2006 du 14 août 2006 consid. 2.3 et les arrêts cités, parmi lesquels l'arrêt 2A.575/1996 du 10 décembre 1996 consid. 2, in RDAF 1997 I p. 29, cité par le recourant; jurisprudence confirmée in ATF 133 II 1 consid. 4.3.3 p. 5), comme la survenance d'un nouveau motif de détention ou la disparition de l'impossibilité dont était affectée le renvoi (arrêt 2A.211/2003 du 5 juin 2003 consid. 3.2). Tel peut par exemple être le cas si l'étranger part dans la clandestinité après la libération de sa première détention (cf. ATF 121 II 110 consid. 2d p. 115). Est aussi envisageable la situation où l'autorité aurait levé une première détention administrative dès lors que l'exécution du renvoi de l'étranger, en soi possible, n'apparaissait plus comme vraisemblable dans un délai utile; en tant que les causes pour la mise en détention de l'étranger persisteraient, cette même autorité pourrait ordonner la réincarcération de celui-ci, si ce renvoi s'avérait par la suite à nouveau vraisemblable dans un délai raisonnable.

5.3 La mise en détention administrative du recourant repose sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr. Cette disposition prévoit 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 qu'elle entende se soustraire au renvoi ou à l'expulsion, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer (cf. ch. 3) ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités (cf. ch. 4). Selon la jurisprudence, un risque de fuite existe notamment lorsque l'étranger a déjà disparu une première fois dans la clandestinité (arrêts 2C_256/2013 du 10 avril 2013 consid. 4.2; 2C_806/2010 du 21 octobre 2010 consid. 2.1; 2C_743/2009 du 7 décembre 2009 consid. 4), qu'il tente d'entraver les démarches en vue de l'exécution du renvoi en donnant des indications manifestement inexactes ou contradictoires ou encore s'il laisse clairement apparaître, par ses déclarations ou son comportement, qu'il n'est pas disposé à retourner dans son pays d'origine (cf. ATF 130 II 56 consid. 3.1 p. 58 s.; arrêt 2C_1139/2012 du 21 décembre 2012 consid. 3.2). Comme le prévoit expressément l'art. 76 al. 1 let. b ch. 3 LEtr, il faut qu'il existe des éléments concrets en ce sens (cf. notamment, arrêts 2C_256/2013 du 10 avril 2013 consid. 4.2; 2C_142/2013 du 1^er mars 2013 consid. 4.2; 2C_1017/2012 du 30 octobre 2012 consid. 4.1.1). Le seul fait de ne pas quitter le pays dans le délai imparti à cet effet ne saurait suffire, pris individuellement, à admettre un motif de détention (cf. arrêt 2C_142/2013 du 1^er mars consid. 4.2 in fine).

5.4 En l'espèce, l'arrêt attaqué retient que le recourant a été placé une première fois en détention administrative. Cette détention a duré un mois, entre le 19 juin et le 19 juillet 2011 (cf. art. 105 al. 2 LTF). Le recourant ne peut donc être détenu sur la base des éléments qui existaient déjà en juin 2011, mais en fonction de nouvelles circonstances.

5.4.1 Pour justifier la seconde mise en détention, objet de la présente procédure, l'arrêt attaqué retient que le recourant a disparu deux fois et a travaillé au noir, ce qui dénote une accoutumance à une vie en marge des lois, de sorte que l'on peut valablement pronostiquer que s'il était relâché, il essaierait de passer dans la clandestinité. Il mentionne aussi, mais sans que l'on saisisse clairement si ces éléments ont joué un rôle dans la mise en détention, que l'intéressé a donné des dates de naissance différentes lors d'interrogatoires en Suisse qu'il ne peut justifier de manière convaincante et que le renvoi n'a pu être exécuté pour des motifs qui lui sont imputables, notamment en lien avec un examen linguistique. En revanche, l'arrêt querellé n'a pas justifié la réincarcération par la disparition d'éventuels obstacles au renvoi (diligent) du recourant.

5.4.2 S'agissant de la première disparition du recourant, elle n'est pas pertinente, dès lors qu'il a été constaté que cette disparition avait été annoncée le 3 octobre 2010, soit avant la première mise en détention. Il en va de même des indications de dates de naissance différentes lors d'interrogatoires que l'arrêt attaqué reproche au recourant d'avoir formulées, sans indiquer quand; cet élément a toutefois déjà été pris en compte par le Juge unique dans son arrêt du 22 juin 2011 confirmant la première mise en détention, en se référant à un interrogatoire du 14 octobre 2008.

En outre, on ne voit pas que le fait que le recourant ait lui-même admis avoir travaillé au noir, infraction qui est du reste passible d'une peine pénale privative de liberté ou d'une peine pécuniaire en vertu de l'art. 115 al. 1 let. c LEtr, constituerait un motif de détention administrative au sens de l'art. 76 al. 1 let. b ch. 3 ou 4 LEtr. Au demeurant, on ignore si ces activités étaient postérieures à la première détention.

Il peut être ajouté que le refus de l'intéressé de retourner dans son pays et son manque de collaboration existaient déjà lors de la première mise en détention.

Le seul motif qui pourrait justifier la détention est ainsi la seconde "disparition" de février 2012. Selon les constatations cantonales, elle consiste dans le fait que le recourant n'a pas avisé les autorités de son déménagement, à cette période, chez une nouvelle compagne qui est enceinte de lui. Dès lors qu'il ne ressort pas de l'arrêt attaqué que le Service cantonal aurait cherché à joindre en vain le recourant, ni que celui-ci se serait caché ou aurait fui, on ne voit pas que l'on puisse déduire de l'absence d'indication quant à son déménagement un élément qui révélerait de manière déterminante et à lui seul un risque concret de passage dans la clandestinité. Le Juge unique retient de manière abstraite que cette "disparition" a empêché une exécution rapide du renvoi de l'intéressé, alors qu'aucun élément ne démontre qu'une telle exécution aurait été concrètement envisagée et organisée par les autorités.

D'ailleurs, ni l'arrêt attaqué ni les autorités cantonale et fédérale ne fournissent d'indication sur les démarches qui auraient été accomplies depuis la première détention du recourant en vue de l'exécution du renvoi. Le dossier ne contient du reste aucune trace de telles démarches. Le Juge unique évoque l'éventualité d'un examen linguistique souvent exigé des Etats de l'Afrique du Nord avant la procédure de laissez-passer, mais il n'apparaît nul part qu'un tel examen aurait été requis par l'Algérie pour le recourant ou qu'il eût été en cours d'organisation durant la période concernée. Partant, on ne voit pas en quoi le comportement de ce dernier aurait pu en avoir empêché la tenue. On ajoutera que, en vue d'assurer la participation de l'étranger dépourvu d'autorisation de séjour en Suisse à un acte ponctuel tendant à établir son identité et sa nationalité, la procédure de rétention administrative visée à l'art. 73 al. 1 let. b LEtr peut selon les circonstances s'avérer davantage proportionnée. Ne pouvant excéder trois jours, la rétention est en effet limitée au temps qui est nécessaire pour garantir la collaboration de la personne concernée ou pour permettre son interrogatoire et, le cas échéant, son transport (al. 2).

En définitive, le seul changement notable des circonstances depuis la première détention du recourant plaide en faveur de sa libération. En effet, le recourant, qui a déjà eu une première fille en Suisse, vit désormais avec une nouvelle compagne de nationalité suisse (art. 105 al. 2 LTF) qui attend un enfant de lui. Or, cet élément tend à réduire fortement le risque que celui-ci ne parte dans la clandestinité et permet du reste de douter de l'imminence de l'exécution du renvoi.

5.5 En conclusion, l'arrêt attaqué ne met en évidence aucune circonstance nouvelle décisive permettant de justifier une seconde mise en détention administrative du recourant en application de l'art. 76 al. 1 ch. 3 et 4 LEtr. La détention du recourant est donc illégale, de sorte que l'arrêt attaqué doit être annulé en ce qu'il approuve la décision du Service cantonal, ce qui justifie de libérer immédiatement l'intéressé.