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é (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é 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. 