Faits:
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é (<ref-law>).
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é en détention pour trois mois au plus X._. 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, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué, à sa mise en liberté immédiate et à l'octroi de l'assistance judiciaire tant sur le plan cantonal que fédéral, Me Michel de Palma étant désigné en qualité d'avocat d'office.
Les autorités concernées, à savoir le Service cantonal, le Tribunal cantonal valaisan et l'Office fédéral ont renoncé à se déterminer.

Considérant en droit:
1.
En matière de mesures de contrainte, la confirmation de la mise en détention prononcée en dernière instance cantonale par le Juge unique du Tribunal cantonal valaisan peut faire l'objet d'un recours en matière de droit public au Tribunal fédéral (cf. arrêt 2C_285/2013 du 23 avril 2013 consid. 1.1). Le recours a été interjeté en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par le détenu administratif qui remplit les conditions de l'<ref-law>. Il convient donc d'entrer en matière.
2.
Le Tribunal fédéral est un juge du droit. Il doit vérifier si, sur la base des faits constatés par l'instance inférieure, le droit a été correctement appliqué (arrêt 2C_142/2013 du 1er mars 2013 consid. 3 et les références citées). L'examen du Tribunal fédéral se fonde donc sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (cf. <ref-ruling> consid. 4.1.2 p. 62; cf. pour la notion d'arbitraire <ref-ruling> consid. 7.1 p. 51) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
3.
L'arrêt attaqué confirme la mise en détention du recourant en application des articles 76 al. 1 let. b ch. 3 et 4 LEtr, relevant en substance que cette mesure est légale, adéquate et proportionnée. Il retient que l'intéressé a disparu deux fois: sa première disparition a été annoncée le 3 octobre 2010; la seconde date en tout cas de janvier 2012, période à laquelle il a déménagé, sans en aviser les autorités, chez une autre femme que celle qui l'avait hébergé à l'issue de sa première détention administrative. Il souligne également que le recourant a travaillé au noir. Ces éléments dénotent, selon le Juge unique, une accoutumance à une vie en marge des lois dont on peut valablement déduire un risque que le recourant ne passe dans la clandestinité pour échapper à son obligation de quitter le territoire suisse. Le Juge unique a en outre relevé que, comme le recourant s'était soustrait au contrôle du Service cantonal, il ne pouvait de bonne foi reprocher à cette autorité d'avoir manqué de célérité dans ses démarches ni arguer d'une impossibilité d'exécuter son renvoi. En effet, les Etats du nord de l'Afrique exigent souvent un examen linguistique préalablement à une demande de laissez-passer, examen qui n'a pu être mené jusqu'à présent pour des motifs imputables au recourant.
4.
Le recourant se plaint en premier lieu d'arbitraire dans l'établissement des faits (voir, pour la notion, <ref-ruling> consid. 4.2 p. 560; arrêt 2C_519/2013 du 3 septembre 2013 consid. 3.1).
Les critiques relatives aux faits ne doivent être examinées que dans la mesure où celles-ci portent sur des éléments qui sont pertinents pour le sort du litige. En l'occurrence, les griefs du recourant concernent des aspects qui ne sont pas indispensables à la résolution du cas. Il n'y a donc pas lieu d'entrer plus avant sur ces questions.
5.
Le recourant se plaint d'une violation de l'art. 76 LEtr.
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. <ref-ruling> 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, RDAF 1997 I 29, cité par le recourant; jurisprudence confirmée in <ref-ruling> 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. <ref-ruling> 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. <ref-ruling> 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 1er 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 1er 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. <ref-law>). 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 d u 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 (<ref-law>) 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é.
6.
Invoquant une violation des art. 9 et 29 al. 3 Cst., le recourant conteste également le refus de l'autorité inférieure de lui accorder l'assistance judiciaire.
Compte tenu de l'issue du litige sur le fond, le grief n'a pas à être traité, car il n'a plus de portée. Il ressort en effet des développements qui précèdent que c'est à tort que le Tribunal cantonal a confirmé la mise en détention du recourant. S'il avait respecté le droit fédéral, il aurait dû lui donner gain de cause en le libérant, ce qui l'aurait amené à allouer à l'avocat de celui-ci une indemnité à titre de dépens, à charge de l'Etat du Valais (Service cantonal), faisant perdre à la requête d'assistance judiciaire son objet. Partant, l'arrêt attaqué doit également être annulé en ce qu'il rejette la demande d'assistance judiciaire du recourant et la cause renvoyée au Tribunal cantonal pour qu'il statue sur les dépens dus à l'avocat de l'intéressé.
7.
En résumé, le recours doit être admis et l'arrêt attaqué annulé, ce qui entraîne le prononcé de la libération immédiate du recourant.
Le dossier sera au surplus renvoyé au Tribunal cantonal pour qu'il octroie à l'avocat du recourant une indemnité à titre de dépens pour la procédure cantonale (cf. art. 67 et 68 al. 5 LTF a contrario).
8.
Compte tenu de l'issue du litige, il sera statué sans frais (<ref-law>). Le canton du Valais supportera les dépens alloués à l'avocat du recourant (cf. <ref-law>), ce qui a pour conséquence de rendre la demande d'assistance judiciaire formée pour la procédure fédérale sans objet (cf. arrêt 2C_1017/2012 du 30 octobre 2012 consid. 5).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est admis et l'arrêt du 18 octobre 2013 est annulé.
2.
Le recourant est immédiatement libéré.
3.
La cause est renvoyée au Tribunal cantonal pour qu'il statue sur les dépens de l'instance cantonale.
4.
Il n'est pas perçu de frais.
5.
Le canton du Valais versera au mandataire du recourant une indemnité de 2'000 fr. à titre de dépens.
6.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrations du canton du Valais, au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 9 décembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton