Sachverhalt:
A. X._ (geb. 1984) stammt aus Algerien. Nach einem erfolglos durchlaufenen Asylverfahren (2004/2005) reiste er im Jahr 2006 erneut in die Schweiz ein und erhielt eine Aufenthaltsbewilligung im Familiennachzug (Verbleib bei seiner Gattin). Seine Aufenthaltsbewilligung wurde mit Verfügung vom 12. November 2010 nicht mehr verlängert und X._ wurde rechtskräftig weggewiesen. Er weigerte sich allerdings, das Land zu verlassen. Am 10. November 2011 scheiterte eine Rückführung nach Algerien an seinem Widerstand, freiwillig auszureisen. Zwangsrückführungen nach Algerien sind derzeit nicht möglich.
B. Nebst dem Strafvollzug befindet sich X._ in ausländerrechtlich begründeter Haft, und zwar vom 3. Mai bis am 14. Juli 2011 (73 Tage) bzw. vom 3. Oktober bis zum 16. November 2011 (45 Tage) in Ausschaffungshaft und seit dem 17. November 2011 (knapp ein Jahr) in Durchsetzungshaft. Mit Verfügung vom 12. September 2012 verlängerte das Migrationsamt des Kantons Basel-Stadt die bis zum 1. Oktober 2012 bestätigte Durchsetzungshaft um weitere zwei Monate bis zum 1. Dezember 2012. Mit Eingabe vom 19. September 2012 verlangte X._ beim Appellationsgericht Basel-Stadt seine Entlassung; am 8. Oktober 2012 gelangte er mit dem Vorbringen an die Vorinstanz, er befinde sich seit dem 2. Oktober 2012 ohne gerichtliche Genehmigung in Haft.
Mit Urteil vom 10. Oktober 2012 bestätigte die Einzelrichterin für Zwangsmassnahmen des Appellationsgerichts Basel-Stadt die von der Migrationsbehörde verlangte Verlängerung Durchsetzungshaft bis zum 1. Dezember 2012.
C. Mit Eingabe vom 2. November 2012 beantragt X._, es sei das Urteil der Einzelrichterin vom 10. Oktober 2012 aufzuheben. Er sei infolge schwerer Verfahrensfehler umgehend aus der Haft zu entlassen. X._ ersucht um unentgeltliche Prozessführung und Verbeiständung.
Das Appellationsgericht Basel-Stadt beantragt, die Beschwerde abzuweisen. Das Bundesamt für Migration hat darauf verzichtet, sich vernehmen zu lassen. X._ hält an seinen Anträgen fest. Ein Gesuch von X._ um Anordnung einer vorsorglichen Haftentlassung (aufschiebende Wirkung) wurde vom Präsidenten mit Verfügung vom 5. November 2012 abgewiesen.
Erwägungen:
1. Gegen letztinstanzliche kantonale richterliche Entscheide betreffend die Zwangsmassnahmen im Ausländerrecht steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen, soweit der Betroffene am vorinstanzlichen Verfahren teilgenommen hat, durch den angefochtenen Entscheid besonders berührt ist und an der Beurteilung seiner Eingabe ein aktuelles praktisches Interesse hat (Art. 86 Abs. 1 und 2, Art. 89 Abs. 1 BGG; vgl. Urteil 2C_10/2009 vom 5. Februar 2009 E. 2, nicht publiziert in BGE 135 II 94; Urteil 2C_624/2011 vom 12. September 2011 E. 1.2). Der Beschwerdeführer ist zweifelsohne zum Rechtsmittel legitimiert: Er befindet sich gestützt auf den hier angefochtenen Entscheid in Haft und hat demnach ein aktuelles Interesse, entlassen zu werden. Ein Ausschlussgrund ist nicht ersichtlich (Art. 83 BGG). Auf die frist- und formgerecht eingereichte Beschwerde ist demnach einzutreten.
2. 2.1 Hat eine ausländische Person ihre Pflicht zur Ausreise aus der Schweiz innerhalb der ihr angesetzten Frist nicht erfüllt und kann die rechtskräftige Weg- oder Ausweisung aufgrund ihres persönlichen Verhaltens nicht vollzogen werden, so darf sie in Durchsetzungshaft genommen werden, um der Ausreisepflicht Nachachtung zu verschaffen, sofern die Anordnung der Ausschaffungshaft nicht zulässig ist oder keine andere, mildere Massnahme zum Ziel führt (Art. 78 Abs. 1 AuG).
Die Haft ist erstmals für einen Monat möglich; sie kann hernach mit der Zustimmung der zuständigen kantonalen gerichtlichen Behörde (vgl. Art. 78 Abs. 2 AuG) jeweils um zwei Monate verlängert werden, sofern die ausländische Person weiterhin nicht bereit ist, ihr Verhalten zu ändern und auszureisen. Die Haft wird gemäss Art. 78 Abs. 6 AuG beendet, wenn eine selbstständige und pflichtgemässe Ausreise nicht möglich ist, obwohl die betroffene Person den behördlich vorgegebenen Mitwirkungspflichten nachgekommen ist (lit. a), oder die Schweiz weisungsgemäss verlassen (lit. b), die Ausschaffungshaft angeordnet (lit. c) oder einem Haftentlassungsgesuch entsprochen wird (lit. d).
2.2 Zweck der Durchsetzungshaft ist es, die ausreisepflichtige Person in jenen Fällen zu einer Verhaltensänderung zu bewegen, in denen nach Ablauf der Ausreisefrist der Vollzug der rechtskräftig gegen sie angeordneten Weg- oder Ausweisung - trotz entsprechender behördlicher Bemühungen - ohne ihre Kooperation nicht (mehr) möglich erscheint. Der damit verbundene Freiheitsentzug stützt sich auf Art. 5 Ziff. 1 lit. f EMRK (Haft zur Sicherung eines schwebenden Ausweisungsverfahrens) und dient in diesem Rahmen der Erzwingung einer durch das Gesetz vorgeschriebenen Verpflichtung (Art. 5 Ziff. 1 lit. b EMRK). Die Durchsetzungshaft bildet das letzte Mittel, wenn und soweit keine andere Massnahme (mehr) zum Ziel führt, den illegal anwesenden Ausländer auch gegen seinen Willen in seine Heimat verbringen zu können. Sie darf - zusammen mit der bereits verbüssten Ausschaffungs- bzw. Vorbereitungshaft - maximal 18 Monate dauern (Art. 78 Abs. 2 i.V.m. Art. 79 AuG), muss aber in jedem Fall verhältnismässig sein. Innerhalb dieser Höchstdauer ist jeweils aufgrund der Umstände im Einzelfall zu prüfen, ob die ausländerrechtliche Festhaltung insgesamt (noch) geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot verstösst (vgl. BGE 135 II 105 E. 2.2.1 S. 107; 134 II 201 E. 2 S. 204 ff.; 134 I 92 E. 2.3 S. 96 ff.; Urteil 2C_639/2011 vom 16. September 2011 E. 3.1; 2C_624/2011 vom 12. September 2011 E. 2.1; 2C_936/2010 vom 24. Dezember 2010 E. 1.2).
2.3 Bei dieser Beurteilung ist dem Verhalten des Betroffenen, den die Papierbeschaffung allenfalls erschwerenden objektiven Umständen (ehemalige Bürgerkriegsregion usw.) sowie dem Umfang der von den Behörden bereits getroffenen Abklärungen Rechnung zu tragen und zu berücksichtigen, wieweit der Ausländer es tatsächlich in der Hand hat, die Festhaltung zu beenden, indem er seiner Mitwirkungs- bzw. Ausreisepflicht nachkommt. Von Bedeutung können zudem seine familiären Verhältnisse sein sowie der Umstand, dass er allenfalls wegen seines Alters oder Gesundheitszustands als besonders schutzbedürftig gelten muss. Das mutmassliche künftige Verhalten des Betroffenen ist jeweils aufgrund sämtlicher Umstände abzuschätzen. Dabei kommt dem Haftgericht wegen der Unmittelbarkeit der Kontakte mit dem Betroffenen ein gewisser Beurteilungsspielraum zu. Ein erklärtes, konsequent unkooperatives Verhalten bildet in diesem Rahmen nur einen - allenfalls aber gewichtigen - Gesichtspunkt unter mehreren. Je länger die ausländerrechtlich motivierte Festhaltung dauert und je weniger die Ausschaffung absehbar erscheint, desto strengere Anforderungen sind an die fortbestehende Hängigkeit des Ausweisungsverfahrens im Sinne von Art. 5 Ziff. 1 lit. f EMRK zu stellen und desto kritischer ist die jeweilige Haftverlängerung zu hinterfragen (vgl. BGE 135 II 105 E. 2.2.2 S. 107 f.; 134 II 201 E. 2 S. 204 ff.; 134 I 92 E. 2.3 S. 96 ff.; Urteil 2C 639/2011 vom 16. September 2011 E. 3.1; 2C_624/2011 vom 12. September 2011 E. 2.1; 2C_936/2010 vom 24. Dezember 2010 E. 1.3).
3. 3.1 Der Beschwerdeführer bringt vor, vom 2. bis zum 10. Oktober 2012 ohne Zustimmung einer gerichtlichen Behörde in Haft gehalten worden zu sein, womit Art. 78 AuG und Art. 5 Abs. 4 EMRK (Anspruch auf rechtzeitige gerichtliche Überprüfung des Freiheitsentzugs) verletzt worden seien. Das Appellationsgericht Basel-Stadt stellt sich demgegenüber auf den Standpunkt, Art. 78 AuG sei nicht verletzt worden; die Verfügung des Migrationsamtes sei von der Haftrichterin gemäss Art. 78 Abs. 4 AuG innerhalb von acht Arbeitstagen zu überprüfen gewesen; mit dem Genehmigungsentscheid am 10. Oktober 2012 sei diese Frist gewahrt worden.
3.2 Die Ausführungen des Appellationsgerichts Basel-Stadt treffen nicht zu:
3.2.1 Der gerichtliche Genehmigungsentscheid zur Verlängerung der Haft ergeht grundsätzlich in einem schriftlichen Verfahren (Art. 78 Abs. 2 AuG). In dieser Bestimmung wird zwar keine Frist explizit erwähnt; gemäss dem Wortlaut ist die Verlängerung der Durchsetzungshaft jedoch nur mit der Zustimmung der kantonalen gerichtlichen Behörde möglich, mit anderen Worten muss die erforderliche Zustimmung durch die gerichtliche Behörde vor Ablauf der bereits genehmigten Haftdauer vorliegen. Diese Interpretation legt nicht nur der Wortlaut nahe, sondern sie ergibt sich auch aus den verfassungs- und völkerrechtlichen Vorgaben (Art. 31 Abs. 4 BV; Art. 5 Abs. 4 EMRK): Der Anspruch auf (rechtzeitige) gerichtliche Überprüfung stellt die zentrale prozessuale Garantie dar, welche vor willkürlichem Entzug der Freiheit schützen soll und für die Interpretation entsprechender Verfahrensbestimmungen massgeblich sein muss (vgl. BGE 137 I 23 E. 2.5 S. 29; 128 II 241 E. 3.5 S. 245; 121 II 105 E. 2c S. 109; Urteil 2C_936/2010 vom 24. Dezember 2010 E. 2.2 f.; vgl. THOMAS HUGI YAR, § 10 Zwangsmassnahmen im Ausländerrecht, in: Uebersax/Rudin/Hugi Yar/Geiser [Hrsg.], Ausländerrecht, 2. Aufl. 2009, N. 10.14 und N. 10.44 ff.).
Um Art. 78 Abs. 2 AuG nicht zu verletzen, muss die Ausländerbehörde somit rechtzeitig um die Haftverlängerung nachsuchen. Erfolgt die gerichtliche Genehmigung nicht innerhalb des ursprünglich genehmigten Zeitraums, ist der Betroffene aus der Haft zu entlassen (vgl. HUGI YAR, a.a.O., N. 10.38; MINH SON NGUYEN, Les renvois et leur exécution en droit suisse, in: AMARELLE/NGUYEN (Hrsg.), Les renvois et leur exécution, 2011, S. 115 ff., S. 181).
3.2.2 Art. 78 Abs. 4 AuG besagt demgegenüber, dass eine Haftverlängerung nur auf Gesuch des Betroffenen hin an einer mündlichen Verhandlung überprüft werden muss. Im Unterschied zur Ausschaffungshaft ist demnach eine mündliche Verhandlung zur Verlängerung der Durchsetzungshaft dann erforderlich, wenn der Betroffene eine solche verlangt; diese hat dann innerhalb von acht Arbeitstagen nach Gesuchseinreichung zu erfolgen (Art. 78 Abs. 4 AuG; vgl. ANDREAS ZÜND, N. 6 zu Art. 78, in: Spescha/Thür/Zünd/Bolzli [Hrsg.], Migrationsrecht, 3. Aufl., 2012; HUGI YAR, a.a.O., N. 10.125). Dabei kann die mündliche Verhandlung, je nach dem Datum des Gesuchseingangs, auch nach Ablauf der zuvor genehmigten Haft erfolgen; in solchen Fällen liegt regelmässig bereits eine schriftliche Zustimmung des kantonalen Haftgerichts vor, die dann an der mündlichen Verhandlung bestätigt wird oder nicht (HUGI YAR, a.a.O., N. 10.125). Ersucht der Betroffene nicht um eine mündliche Verhandlung, so kommt entgegen der Ansicht der Vorinstanz zum Vornherein nicht Art. 78 Abs. 4 AuG zur Anwendung. Vielmehr ergeht der Genehmigungsentscheid schriftlich nach den Vorgaben von Art. 78 Abs. 2 AuG.
Die vorinstanzliche Interpretation von Art. 78 Abs. 2 und 4 AuG (vgl. oben E. 3.1) hätte zur Folge, dass der Freiheitsentzug im Falle der Haftverlängerung bis zur gerichtlichen Genehmigung mit acht Arbeitstagen mehr als doppelt so lange dauern dürfte als bei der erstmaligen Anordnung der Haft (96 Stunden), obwohl bei Letzterer eine vorherige gerichtliche Überprüfung nicht möglich ist. Keinesfalls kann sich jedoch eine gerichtliche Behörde, welche über die Genehmigung der Verlängerung der Durchsetzungshaft zu befinden hat, auf eine Frist berufen, die zur Beschleunigung des Verfahrens zugunsten des Inhaftierten bei der Durchführung einer mündlichen Verhandlung dient (Art. 78 Abs. 4 AuG), um ihrerseits mit dem erforderlichen Genehmigungsentscheid zuzuwarten und damit das Verfahren zu verzögern.
3.2.3 Im vorliegenden Verfahren hat der Beschwerdeführer mit Eingabe vom 19. September 2012 ausdrücklich auf eine mündliche Verhandlung für den gerichtlichen Genehmigungsentscheid zur Verlängerung der Durchsetzungshaft verzichtet. Die Haft wäre gemäss Art. 78 Abs. 2 AuG mit vorgängiger Zustimmung der kantonalen gerichtlichen Behörde um zwei Monate zu verlängern gewesen. Dies bedeutet, dass der Genehmigungsentscheid vor dem 1. Oktober 2012 und nicht erst am 10. Oktober 2012 hätte vorliegen müssen. Der Beschwerdeführer ist somit (auf eine zu genehmigende Verlängerungsdauer von 2 Monaten) mehr als eine Woche ohne Bestätigungsentscheid festgehalten worden. Seine zentrale prozessuale Garantie auf rechtzeitige gerichtliche Prüfung ist in gravierender Weise missachtet worden. Das Appellationsgericht des Kantons Basel-Stadt hat demnach Art. 78 Abs. 2 AuG, Art. 31 Abs. 4 BV und Art. 5 EMRK verletzt. Es liegt ein schwerwiegender Verfahrensfehler vor.
4. 4.1 Den verfahrensrechtlichen Garantien kommt bei den Zwangsmassnahmen im Ausländerrecht grundsätzliche Bedeutung zu; das Bundesgericht achtet besonders streng auf deren Einhaltung (vgl. oben E. 3.2.1 und 3.2.3; BGE 137 I 23 E. 2.5 S. 29; 128 II 241 E. 3.5 S. 245; 121 II 105 E. 2c S. 109; Urteil 2C_936/2010 vom 24. Dezember 2010 E. 2.3; HUGI YAR, a.a.O., N. 10.14 und N. 10.44 ff.). Gleichwohl führt eine Verletzung von Verfahrensvorschriften nicht immer zu einer Haftentlassung: Nach der Rechtsprechung kommt es vielmehr einerseits darauf an, welche Bedeutung den verletzten Vorschriften für die Wahrung der Rechte des Betroffenen zukommt, andererseits kann das Anliegen einer reibungslosen Durchsetzung der Ausschaffung der Freilassung entgegenstehen, wenn der Ausländer die öffentliche Sicherheit oder Ordnung gefährdet (vgl. BGE 121 II 105 E. 2c S. 109, 110 E. 2a S. 113; 121 II 110 E. 2 S. 113 ff.; 122 II 154 E. 3 S. 158 f.; Urteil 2C_936/2010 vom 24. Dezember 2010 E. 2.3; 2C_60/2007 vom 10. April 2007 E. 2.3.3).
4.2 Zu prüfen ist demnach, ob allfällige öffentliche Interessen (öffentliche Ordnung und Sicherheit) am Fortbestehen der Durchsetzungshaft den gravierenden Verfahrensmangel vorliegend tatsächlich aufzuwiegen vermögen. Der Beschwerdeführer hat Delikte begangen (Verurteilungen u.a. wegen gewerbsmässigen Diebstahls und geringfügigen Übertretungen gegen das Betäubungsmittelgesetz [regelmässiger Kauf und Konsum von Cannabis; 50 Gramm]), welche die öffentliche Ordnung beeinträchtigt haben, und ein entsprechendes Verhalten ist auch weiterhin nicht auszuschliessen. Jedoch liegt ein besonders schwerwiegender Verfahrensfehler vor, indem der Beschwerdeführer während mehr als einer Woche widerrechtlich festgehalten wurde (vgl. E. 3.2.3). Die vom Beschwerdeführer begangenen Delikte haben nicht das Gewicht, diesen Verfahrensmangel aufzuwiegen.
Dies gilt umso mehr, als sich der Beschwerdeführer bereits sehr lange in ausländerrechtlich begründeter Haft befindet. Er war im Jahr 2011 rund vier Monate in Ausschaffungshaft und zuletzt ein Jahr in Durchsetzungshaft, sodass die ausländerrechtlich motivierte Festhaltung bereits 16 Monate andauert und die gesetzlich zulässige Höchstdauer von 18 Monaten (Art. 78 i.V.m. 79 Abs. 1 und 2 AuG) in Kürze erreicht sein wird.
5. Der Beschwerdeführer ist demnach unverzüglich aus der Haft zu entlassen. Unbenommen ist es der Behörde allerdings, gegenüber dem Beschwerdeführer eine Eingrenzung anzuordnen (Art. 74 Abs. 1 lit. b AuG). Zweck dieser Massnahme ist es, den Verbleib der ausländischen Person zu kontrollieren sowie ihre Verfügbarkeit für die Vorbereitung und Durchführung der Ausschaffung weiterhin sicherzustellen (ZÜND, a.a.O., N. 5 zu Art. 74 AuG). Sie ist milderes Mittel zum ausländerrechtlich begründeten Freiheitsentzug und kann und darf analog diesem auch eine gewisse Druckwirkung zur Durchsetzung der Ausreisepflicht entfalten. Die Missachtung einer Ein- oder Ausgrenzung kann mit Freiheitsstrafe bis zu drei Jahren oder einer Geldstrafe geahndet werden (Art. 119 AuG; vgl. Urteil 2C_1044/2012 vom 5. November 2012 E. 3.1).
6. 6.1 Die Beschwerde ist demnach gutzuheissen, der angefochtene Entscheid des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichterin für Zwangsmassnahmen im Ausländerrecht, ist aufzuheben.
6.2 Dem Verfahrensausgang entsprechend werden keine Kosten erhoben (Art. 66 Abs. 1 und 4 BGG). Mit der Gutheissung der Beschwerde wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos. Der Kanton Basel-Stadt wird entschädigungspflichtig (Art. 68 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichterin für Zwangsmassnahmen im Ausländerrecht, wird aufgehoben. Der Beschwerdeführer ist unverzüglich aus der Haft zu entlassen.
2. 2.1 Es werden keine Kosten erhoben.
2.2 Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
2.3 Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, Einzelrichterin für Zwangsmassnahmen im Ausländerrecht, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 22. November 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni