Sachverhalt: A. A._ stammt eigenen Angaben zufolge aus Algerien. Im März 2013 stellte er in der Schweiz ein Asylgesuch. Darauf trat das Bundesamt für Migration (BFM; heute: Staatssekretariat für Migration [SEM]) mit Verfügung vom 18. Juli 2013 nicht ein. Der daraufhin ergangenen Wegweisungsanordnung leistete A._ keine Folge; stattdessen wurde er in der Schweiz straffällig und erwirkte unter anderem wegen gewerbs- und bandenmässigen Diebstahls, Hausfriedensbruchs, rechtswidriger Einreise und rechtswidrigen Aufenthalts mehrere Haftstrafen. Kurz vor Beendigung des Strafvollzugs verfügte das Migrationsamt des Kantons Basel-Stadt (nachfolgend: Migrationsamt) am 7. Dezember 2018 eine dreimonatige Ausschaffungshaft. Die Einzelrichterin des Appellationsgerichts Basel-Stadt für Zwangsmassnahmen im Ausländerrecht (nachfolgend: die Einzelrichterin) bestätigte die angeordnete Ausschaffungshaft mit Urteil vom 10. Dezember 2018, beschränkte die Haftdauer indes auf einen Monat. B. B.a. Mit Verfügung vom 3. Januar 2019 hob das Migrationsamt die Ausschaffungshaft auf und verfügte stattdessen eine Durchsetzungshaft von einem Monat. Mit Urteil vom 7. Januar 2019 bestätigte die Einzelrichterin diese Durchsetzungshaft. Mit Verfügung vom 30. Januar 2019 stimmte die Einzelrichterin auch der vom Migrationsamt verfügten Verlängerung der Durchsetzungshaft bis zum 2. April 2019 zu; ihre Zustimmung hielt sie auch nach einer im Beisein des amtlichen Rechtsbeistands durchgeführten Gerichtsverhandlung aufrecht. Ein weiteres Mal verlängerte das Migrationsamt mit Verfügung vom 21. März 2019 die Durchsetzungshaft um zwei Monate. Auch diese Verlängerung wurde von der Einzelrichterin mit Verfügung vom 29. März 2019 beziehungsweise mit dem nach mündlicher Verhandlung ergangenen Urteil vom 8. April 2019 geschützt. B.b. Zuletzt verlängerte das Migrationsamt die Ausschaffungshaft mit Verfügung vom 23. Mai 2019 um weitere zwei Monate. Mit Verfügung vom 29. Mai 2019 schützte die Einzelrichterin auch diesen Entscheid. A._ verlangte in der Folge eine mündliche Verhandlung unter Beigabe eines unentgeltlichen Rechtsbeistands in der Person eines namentlich benannten Rechtsanwalts. Mit Verfügung vom 3. Juni 2019 setzte die Einzelrichterin auf den 5. Juni 2019 eine Verhandlung an, wies das Gesuch um Beiordnung eines unentgeltlichen Rechtsbeistands hingegen ab. Nach Durchführung der Verhandlung am 5. Juni 2019 stellte die Einzelrichterin mit gleichentags ergangenem Urteil fest, die Verlängerung der Durchsetzungshaft über A._ sei bis zum 2. August 2019 rechtmässig und angemessen. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 1. Juli 2019 gelangt A._ an das Bundesgericht und beantragt die Aufhebung des Urteils der Einzelrichterin des Appellationsgerichts Basel-Stadt vom 5. Juni 2019 und die Anweisung an das Migrationsamt, ihn aus der Durchsetzungshaft zu entlassen und umgehend auf freien Fuss zu setzen; weiter sei festzustellen, dass er in seinen Rechten aus Art. 6 Abs. 2 lit. c EMRK sowie Art. 29 BV verletzt sei. Mit Präsidialverfügung vom 3. Juli 2019 verzichtet das Bundesgericht antragsgemäss auf die Erhebung eines Kostenvorschusses. Das Migrationsamt und die Einzelrichterin des Appellationsgerichts beantragen die Abweisung der Beschwerde. Das SEM verzichtet auf Vernehmlassung. A._ repliziert.