Faits :
A.
A.a. A._ est né en 1977 et indique être originaire d'Algérie. Par jugement du 14 novembre 2019, le Tribunal de police du canton de Genève (ci-après: le Tribunal de police) l'a condamné à une peine privative de liberté de douze mois pour vols, menaces, injures, non-respect de l'interdiction de pénétrer dans une région déterminée, rupture de ban, voies de fait et consommation de stupéfiants. Cette autorité a également ordonné son expulsion de Suisse pour une durée de cinq ans. Ce jugement a été confirmé par arrêt du 24 février 2020 de la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève, puis par arrêt du 11 juin 2020 du Tribunal fédéral (arrêt 6B_443/2020).
A.b. Le 3 août 2020, l'Office cantonal de la population et des migrations du canton de Genève (ci-après: l'Office cantonal) a notifié à A._ une décision de non-report de son expulsion judiciaire. Le 14 août 2020, le Commissaire de police du canton de Genève l'a placé en détention administrative. Par jugement du 17 août 2020, le Tribunal administratif de première instance du canton de Genève (ci-après: le Tribunal administratif) a confirmé l'ordre de mise en détention. Devant cette autorité, A._ a notamment indiqué que ses documents d'identité algériens se trouvaient en Algérie et qu'il possédait également la nationalité tunisienne, bien qu'il n'ait aucune attache avec la Tunisie.
Par arrêt du 4 septembre 2020, la Chambre administrative de la Cour de justice (ci-après: la Cour de justice) a annulé ce jugement, l'expulsion de l'intéressé vers la Tunisie ou l'Algérie étant impossible dans un délai raisonnable compte tenu du contexte de pandémie.
Par pli remis en mains propres le 4 septembre 2020, l'Office cantonal a imparti à A._ un délai de vingt-quatre heures pour quitter le territoire suisse. Une carte d'annonce de sortie lui a également été remise et il a été averti qu'il s'exposait à une condamnation pénale pour rupture de ban s'il ne quittait pas la Suisse dans le délai imparti.
Par jugement du 30 octobre 2020, le Tribunal de police du canton de Genève (ci-après: le Tribunal de police) a condamné A._ pour rupture de ban et, ce dernier étant alors détenu, il a ordonné sa libération immédiate.
B.
B.a. Par courrier du 2 novembre 2020 adressé à l'Office cantonal, A._ a demandé à être admis provisoirement sur le territoire cantonal. Il demandait qu'une décision d'interdiction de quitter le territoire cantonal lui soit notifiée.
Le 5 novembre 2020, l'Office cantonal a répondu à A._ que le prononcé d'une telle mesure relevait de la compétence du Commissaire de police. Cette autorité lui a également rappelé qu'en qualité de ressortissant tunisien auquel un laissez-passer avait été délivré par les autorités tunisiennes en 2012, il n'était pas empêché de rentrer dans ce pays.
Le 10 novembre 2020, A._ a déposé un recours auprès du Tribunal administratif concluant à l'annulation de la "décision" du 5 novembre 2020 de l'Office cantonal. Par jugement du 13 novembre 2020, le Tribunal administratif a déclaré le recours irrecevable au motif que l'acte attaqué ne constituait pas une décision.
B.b. Le 17 novembre 2020, A._ a mis en demeure l'Office cantonal de rendre une décision formelle au sujet de sa demande du 2 novembre 2020. Ce courrier a été transmis au Commissaire de police pour raisons de compétences.
Le 19 novembre 2020, le Commissaire de police a indiqué à l'intéressé qu'il n'entendait pas prendre de mesures de contrainte à son encontre, étant rappelé que le prononcé d'une telle mesure constituait, selon la loi, une faculté et non une obligation.
Le recours déposé par A._ contre cette décision a été déclaré irrecevable par le Tribunal administratif le 27 novembre 2020, faute d'intérêt digne de protection à l'annulation de la décision attaquée.
Depuis le 13 décembre 2020, A._ est à nouveau détenu, notamment pour rupture de ban et infraction à la LEI.
B.c. Par arrêt du 11 mai 2021, la Cour de justice a rejeté les recours formés par A._ contre les jugements d'irrecevabilité du Tribunal administratif des 13 et 27 novembre 2020, après avoir joint les deux causes.
C.
Par acte du 24 juin 2021, A._ dépose un recours en matière de droit public auprès du Tribunal fédéral contre l'arrêt de la Cour de justice du 11 mai 2021. Il requiert principalement, sous suite de dépens, l'annulation de l'arrêt attaqué, son assignation à un lieu de résidence, le constat que le courrier de l'Office cantonal du 2 novembre (recte: 5 novembre) 2020 est une décision, et le renvoi de la cause à l'autorité précédente pour nouvelle décision sur les frais et dépens de la procédure cantonale. Subsidiairement, il conclut au renvoi de la cause à la Cour de justice pour nouvelle décision au sens des considérants. Il sollicite aussi le bénéfice de l'assistance judiciaire.
La Cour de justice renonce à formuler des observations et persiste dans les considérants et le dispositif de son arrêt. Invités à se déterminer, l'Office cantonal et le Secrétariat d'Etat aux migrations n'ont pas déposé d'observations.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office (<ref-law>) et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2).
1.1. La voie du recours en matière de droit public est en principe ouverte à l'encontre des décisions cantonales en matière de mesures de contrainte (<ref-law>; cf. <ref-ruling> consid. 1.1.3; arrêt 2C_984/2020 du 7 janvier 2021 consid. 1.1).
1.2. Dirigé contre un arrêt final (<ref-law>) rendu en dernière instance cantonale par une autorité judiciaire supérieure (art. 86 al. 1 let. d et al. 2 LTF), le recours a été déposé en temps utile (<ref-law>) par le destinataire de l'acte attaqué. S'agissant d'un recours contre un arrêt cantonal confirmant des jugements d'irrecevabilité, le recourant, qui a participé à la procédure devant l'autorité précédente, a un intérêt digne de protection au sens de l'<ref-law> à se plaindre que l'arrêt confirmant lesdits jugements d'irrecevabilité viole le droit fédéral, de sorte qu'il faut lui reconnaître la qualité pour recourir. Le recours est, dès lors, recevable sur ce point.
1.3. En vertu de l'art. 42 al. 1 et 2 LTF, le recourant doit motiver son recours en exposant succinctement en quoi la décision attaquée viole le droit. En particulier, la motivation doit se rapporter à l'objet du litige tel qu'il est circonscrit par la décision litigieuse (<ref-ruling> consid. 6.4). Lorsque celle-ci confirme une décision d'irrecevabilité, les motifs développés dans le mémoire de recours doivent porter sur la question de la recevabilité traitée par l'instance précédente à l'exclusion du fond du litige (cf. <ref-ruling> consid. 1b; arrêt 2C_225/2020 du 18 septembre 2020 consid. 1.6.1).
2.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral contrôle librement le respect du droit fédéral et du droit international (cf. <ref-law>; arrêt 2C_887/2020 du 18 août 2021 consid. 2.1). Sous réserve des cas non pertinents visés à l'art. 95 let. c à e LTF, le recours en matière de droit public ne peut pas être formé pour violation du droit cantonal en tant tel. Il est néanmoins possible de faire valoir que l'application du droit cantonal consacre une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à un autre droit fondamental (cf. <ref-ruling> consid. 6.1). Le Tribunal fédéral n'examine toutefois le moyen tiré de la violation de droits fondamentaux et du droit cantonal que si ce grief a été invoqué et motivé de manière précise par le recourant (<ref-law>).
2.2. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits constatés par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Selon l'<ref-law>, le recours ne peut critiquer les constatations de fait que si les faits ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire - ou en violation du droit au sens de l'<ref-law> et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-ruling> consid. 6). Conformément à l'<ref-law>, la partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 6.3). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal fédéral (<ref-law>).
En l'espèce, le recourant complète librement l'état de fait retenu dans l'arrêt attaqué, sans expliquer précisément en quoi l'autorité précédente aurait établi les faits de manière arbitraire. Il en va notamment ainsi lorsqu'il allègue que les autorités cantonales ne lui ont jamais délivré de carte d'annonce de sortie lors de sa libération immédiate prononcée par le Tribunal de police le 30 octobre 2020. Le Tribunal fédéral ne peut par conséquent pas tenir compte de ses ajouts et statuera en se fondant sur les faits qui ressortent de l'arrêt entrepris.
Pour le surplus, la pièce postérieure à l'arrêt attaqué produite par le recourant, à savoir l'ordonnance du 19 juillet 2021 de la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève ordonnant sa mise en liberté, ne saurait être prise en considération. Cette pièce, de même que les faits qui en découlent, sont nouveaux et, partant, irrecevables.
3.
Dans un grief formel qu'il convient d'examiner en premier lieu (<ref-ruling> consid. 3), le recourant se plaint d'une violation de son droit d'être entendu, au sens de l'art. 29 al. 2 Cst., en relation avec l'établissement des faits par la Cour de justice. Selon lui, cette autorité aurait pris en compte un jugement qu'elle avait rendu le 29 novembre 2011 dans une procédure à laquelle le recourant était partie, sans toutefois l'aviser que ledit jugement avait été versé au dossier et sans qu'il ait pu s'exprimer sur son contenu.
3.1. Le droit d'être entendu de l'art. 29 al. 2 Cst. comprend le droit pour l'intéressé de s'exprimer sur tous les éléments pertinents avant qu'une décision touchant sa situation juridique ne soit rendue (<ref-ruling> consid. 2.3). Ainsi, l'autorité judiciaire qui envisage de fonder sa décision sur des nouvelles pièces est tenue d'en aviser les parties et de les inviter à s'exprimer à leur sujet sous peine de violer leur droit d'être entendu (<ref-ruling> consid. 1.1). Il n'y a cependant pas lieu d'administrer des preuves sur des faits notoires ou, autrement dit, sur ceux dont l'existence est certaine au point d'emporter la conviction du juge, qu'il s'agisse de faits connus de manière générale du public ou seulement du juge (cf. <ref-ruling> consid. 1.1.1).
3.2. En l'espèce, la Cour de justice se réfère explicitement dans l'arrêt attaqué à un jugement qu'elle a rendu le 29 novembre 2011 et qui portait sur la conformité de la détention administrative du recourant dans l'attente de son renvoi vers l'Algérie ou la Tunisie. Les éléments de ce jugement repris dans l'arrêt attaqué mettent principalement en exergue l'existence d'un acte de naissance attestant de la nationalité algérienne du recourant, des indices que ce dernier avait grandi et avait était socialisé en Algérie, des déclarations de l'intéressé selon lesquelles il était de nationalité tunisienne et algérienne mais que l'Algérie était son pays de socialisation, et des tractations en cours tant avec les autorités tunisiennes qu'algériennes en vue de son refoulement.
Contrairement à ce qu'allègue le recourant, l'autorité précédente n'était pas tenue de l'informer de la teneur du jugement du 29 novembre 2011 dans la mesure où, étant lui-même destinataire dudit jugement, il ne pouvait en ignorer la teneur. Au demeurant, les éléments dudit jugement mentionnés dans l'arrêt attaqué ne font que corroborer d'autres pièces du dossier en possession des juges précédents au moment de rendre l'arrêt attaqué. En effet, le recourant a expressément reconnu, dans le cadre de la procédure devant le Tribunal administratif ayant abouti à l'arrêt du 17 août 2020, qu'il possédait des documents d'identité algériens et qu'il était également de nationalité tunisienne. Par ailleurs, l'arrêt attaqué mentionne qu'en novembre 2020, les autorités tunisiennes ont identifié le recourant et étaient disposées à lui délivrer un laissez-passer. On ne voit dès lors pas en quoi l'administration du jugement du 29 novembre 2011, dont le contenu ne fait que corroborer plusieurs autres pièces du dossier, dont les propres déclarations du recourant, était susceptible de modifier la conviction des juges précédents ou d'influer sur le sort de la cause. Partant, la Cour de justice n'avait pas à donner communication de l'arrêt du 29 novembre 2011 au recourant et on ne discerne aucune violation de l'art. 29 al. 2 Cst. Ce grief est donc mal fondé.
4.
Le litige porte sur le point de savoir si c'est à bon droit que la Cour de justice a rejeté les recours du recourant dirigés contre les jugements du Tribunal administratif du 13 novembre 2020 et du 27 novembre 2020 déclarant irrecevables les recours de l'intéressé contre le refus des autorités administratives de donner suite à ses requêtes tendant à ce qu'une assignation à résidence soit prononcée à son encontre.
4.1. Dans son arrêt du 11 mai 2021, la Cour de justice a indiqué que l'assignation à un lieu de résidence, au sens de l'art. 74 al. 1 LEI, est une disposition rédigée en la forme potestative qui ne confère pas de droit au justiciable. Le prononcé d'une telle mesure de contrainte ne constituait ainsi pas un droit et ne procurerait aucun avantage de nature économique, matérielle ou idéale au recourant. Dès lors, quand bien même le recourant remplissait toutes les conditions matérielles posées par cette disposition, il ne disposerait en aucun cas d'un droit à ce qu'elle soit prononcée. Il serait d'ailleurs difficilement concevable qu'une mesure de contrainte, qui vise à restreindre les droits de la personne concernée, puisse être perçue comme une mesure visant à la protéger et à laquelle elle aurait un droit.
4.2. Selon le recourant, l'art. 74 al. 1 LEI consacrerait un droit à se voir assigner un lieu de résidence, de sorte que c'est à tort que les autorités cantonales ont renoncé à prononcer une telle mesure.
4.3. A teneur de l'art. 74 al. 1 LEI, l'autorité cantonale compétente peut enjoindre à un étranger de ne pas quitter le territoire qui lui est assigné ou de ne pas pénétrer dans une région déterminée lorsqu'il n'est pas titulaire d'une autorisation de courte durée, d'une autorisation de séjour ou d'une autorisation d'établissement et qu'il trouble ou menace la sécurité et l'ordre publics (let. a); lorsqu'il est frappé d'une décision de renvoi ou d'expulsion entrée en force et que des éléments concrets font redouter qu'il ne quittera pas la Suisse dans le délai prescrit ou qu'il n'a pas respecté le délai qui lui était imparti pour quitter le territoire (let b.); ou encore lorsque l'exécution du renvoi ou de l'expulsion a été reportée conformément à l'art. 69 al. 3 LEI (let. c). La mesure d'assignation d'un lieu de résidence, respectivement d'interdiction de pénétrer dans une région déterminée doit au demeurant respecter le principe de proportionnalité (<ref-ruling> consid. 2.3 et les références).
L'assignation à résidence figure à la section 5 du chapitre 10 de la LEI consacrée aux mesures de contrainte. Il s'agit ainsi d'une mesure privant la personne qui se la voit imposer de sa liberté de mouvement et à laquelle l'étranger doit impérativement se soumettre, même contre son gré (cf. Chatton/Merz, in Code annoté de droit des migrations, vol. II: Loi sur les étrangers [LEtr], 2017 no 3 et 5 ad art. 74 LEtr). Une mesure de contrainte ne saurait ainsi être conçue comme un droit auquel la personne qui en remplirait les conditions pourrait prétendre. Le texte de l'art. 74 al. 1 LEI le démontre du reste. Ainsi, cette mesure est conçue comme une faculté reconnue à l'autorité cantonale compétente, qui dispose d'un large pouvoir d'appréciation et qui ne peut la prononcer que dans le respect du principe de proportionnalité (Chatton/Merz, op. cit. no 10 ad art. 74 LEtr). Le législateur a en effet renoncé à exiger le prononcé automatique de mesures de contrainte (cf. le classement de la Motion Brand 13.3913 "Loi sur les étrangers. Durcir les mesures de restriction de la liberté de mouvement", qui visait à modifier l'article 74 al. 1 LEI pour imposer l'assignation à un lieu de résidence lorsque les conditions étaient remplies).
4.4. Il découle de ce qui précède que si une autorité renonce à prononcer une assignation à résidence, la personne concernée demeure libre de restreindre volontairement sa liberté de mouvement en choisissant de rester dans un territoire donné, mais elle n'a aucun droit au prononcé d'une telle assignation. Ainsi, les développements du recourant visant à établir qu'il remplit les conditions visées par cette disposition, et notamment celles de l'art. 69 al. 3 LEI auquel renvoie l'art. 74 al. 1 let. c LEI, ou qu'une demande d'admission provisoire aurait dû être adressée au SEM, au sens de l'art. 83 LEI, sont ainsi sans pertinence.
Dès lors, la Cour de justice n'a pas violé l'art. 74 al. 1 LEI en confirmant, que faute de droit à se voir assigner à résidence, le recourant ne possédait pas la qualité pour recourir contre la décision du Commissaire de police refusant de prononcer une telle assignation. Le grief est par conséquent mal fondé.
5.
Le recourant reproche également aux juges précédents d'avoir violé l'art. 12B de la loi genevoise d'application de la loi fédérale sur les étrangers du 16 juin 1988 (LaLEtr; RS/GE F 2 10) en confirmant le refus des autorités cantonales d'accéder à sa demande d'assignation territoriale.
Dans la mesure toutefois où le recourant n'invoque la violation d'aucun droit fondamental et ne fait pas non plus valoir que l'application de l'art. 12B LaLEtr par les autorités cantonales serait arbitraire, son grief ne répond pas aux exigences accrues de motivation de l'<ref-law> (cf. supra consid. 2.1). Au surplus, le présent litige porte uniquement sur la question de l'entrée en matière sur les recours de l'intéressé visant à obtenir le prononcé d'une mesure de contrainte au sens de l'art. 74 LEI, de sorte que ce grief dépasse l'objet du litige et n'a donc pas à être examiné (cf. supra consid. 1.3). En tout état de cause, l'autorité précédente avait d'emblée relevé que cette critique ne figurait pas dans les demandes initiales du recourant et que l'art. 12B LaLEtr ne trouvait pas à s'appliquer en l'espèce. Le recourant ne saurait donc a fortiori s'en plaindre en première instance devant le Tribunal fédéral.
6.
Le recourant a sollicité le bénéfice de l'assistance judiciaire. La cause paraissant d'emblée dépourvue de chances de succès, cette requête doit être rejetée (<ref-law>). Les frais seront donc mis à la charge du recourant, qui succombe, mais fixés en tenant compte de sa situation financière précaire (art. 65 al. 2 et 66 al. 1 LTF). Il ne sera pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté, dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué au mandataire du recourant, à la Cour de justice de la République et canton de Genève, Chambre administrative, 2ème section, à l'Office cantonal de la population et des migrations du canton de Genève, au Commissaire de police du canton de Genève, et au Secrétariat d'Etat aux migrations.
Lausanne, le 29 mars 2022
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
La Présidente : F. Aubry Girardin
La Greffière : S. Colella