Faits:
A. Ressortissant algérien né en février 1981, X._ a fait l'objet d'un premier rapport de police le 10 août 2006 pour violation de la législation sur les étrangers. Entre avril 2008 et septembre 2010, il a été condamné à huit reprises pour vols et infraction à la législation sur les étrangers, la dernière fois à une peine privative de liberté de huit mois.
Le 26 août 2008, l'Office fédéral des migrations (ODM) a prononcé à l'encontre de X._ une interdiction d'entrée en Suisse valable jusqu'au 2 septembre 2013 qui est entrée en force. Les autorités algériennes, qui avaient identifié l'intéressé comme l'un de leurs ressortissants, ont indiqué qu'elles acceptaient d'établir un laissez-passer en vue de son renvoi. L'ODM en a informé la police judiciaire de Genève en janvier 2009.
Le 20 mars 2009, l'Office cantonal genevois de la population (ci-après l'Office cantonal) a prononcé une décision de renvoi de Suisse à l'encontre de X._, exécutoire dès l'accomplissement de sa dernière peine privative de liberté.
B. Le 18 avril 2011, X._, qui avait fini de purger sa dernière condamnation, a été placé en détention administrative pour une durée d'un mois en vue de son renvoi, décision confirmée le 21 avril 2011 par le Tribunal administratif de première instance du canton de Genève (ci-après le TAPI), l'intéressé s'opposant à son retour en Algérie, en raison des conditions de vie difficiles. Le 12 mai 2011, la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours formé par X._ à l'encontre de la décision du TAPI.
Entre-temps, le 28 avril 2011, X._ avait refusé d'embarquer dans un vol à destination d'Alger. Après avoir réitéré son refus de retourner en Algérie aux autorités genevoises, il a fait l'objet, le 17 mai 2011, d'une décision de détention pour insoumission d'une durée d'un mois, confirmée par le TAPI le 19 mai 2011. Son recours auprès de la Cour de justice a été rejeté le 8 juin 2011. Par arrêt du 21 juillet 2011, le Tribunal fédéral a déclaré irrecevable le recours en matière de droit public déposé par l'intéressé (cause 2C_575/2011).
Le 21 juillet 2011, X._ s'est à nouveau opposé à monter dans l'avion qui devait le rapatrier à Alger.
C. A la suite d'une requête de l'Office cantonal du 9 août 2011, le TAPI a autorisé, le 11 août 2011, la prolongation de la détention pour insoumission de X._ pour une durée de deux mois, jusqu'au 8 octobre 2011.
Par arrêt du 23 août 2011, la Cour de justice a rejeté le recours formé par X._ contre le jugement du TAPI du 11 août 2011.
D. A l'encontre de cet arrêt, X._ interjette un recours en matière de droit public au Tribunal fédéral, dans lequel il conclut à l'annulation de la décision attaquée et à ce que sa mise en liberté soit ordonnée. Il demande par ailleurs le bénéfice de l'assistance judiciaire.
La Police genevoise et l'Office cantonal ont déclaré renoncer à formuler des observations, à l'instar de la Cour de justice, qui persiste dans les considérants et le dispositif de son arrêt. L'ODM n'a pas répondu dans le délai imparti à cet effet.
Considérant en droit:
1. 1.1 En matière de mesures de contrainte, le recours en matière de droit public est en principe ouvert (art. 82 ss LTF; arrêt 2C_10/2009 du 5 février 2009 consid. 2, non publié aux ATF 135 II 94).
1.2 Dirigé contre un arrêt final, émanant d'une autorité judiciaire cantonale supérieure de dernière instance (cf. art. 86 al. 1 let. d et al. 2 LTF), le présent recours a été formé en temps utile (art. 100 LTF) et dans les formes requises (art. 42 LTF) par le recourant qui, en vertu de la décision attaquée, voit sa détention pour insoumission prolongée jusqu'au 8 octobre 2011, de sorte qu'il a un intérêt actuel digne de protection à agir (art. 89 LTF).
2. Saisi d'un recours en matière de droit public, le Tribunal fédéral revoit librement l'application du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'art. 106 al. 2 LTF. Aux termes de cet alinéa, le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant.
3. 3.1 A la suite de sa détention en vue du renvoi, le recourant a été placé en détention pour insoumission, ce qui est possible, pour autant que les conditions de l'art. 78 al. 1 LEtr soient remplies (cf. art 78 al. 3 LEtr).
Selon l'art. 78 al. 1 LEtr, si l'étranger n'a pas obtempéré à l'injonction de quitter la Suisse dans le délai prescrit et que la décision exécutoire de renvoi ou d'expulsion ne peut être exécutée en raison de son comportement, il peut être placé en détention afin de garantir qu'il quittera effectivement le pays, pour autant que les conditions de la détention en vue du renvoi ou de l'expulsion ne soient pas remplies et qu'il n'existe pas d'autres mesures moins contraignantes susceptibles de conduire à l'objectif visé. Le but de la détention pour insoumission est de pousser un étranger tenu de quitter la Suisse à changer de comportement lorsque, à l'échéance du délai de départ, l'exécution de la décision de renvoi entrée en force ne peut être assurée sans la coopération de l'étranger malgré les efforts des autorités (cf. art. 78 LEtr; ATF 135 II 105 consid. 2.2.1 p. 107). La détention pour insoumission apparaît comme une ultima ratio, dans la mesure où il n'existe plus d'autres mesures permettant d'aboutir à ce que l'étranger présent illégalement en Suisse puisse être renvoyé dans son pays. Selon la jurisprudence, elle doit en tous les cas respecter le principe de la proportionnalité et suppose d'examiner l'ensemble des circonstances pour déterminer si elle paraît appropriée et nécessaire (cf. ATF 135 II 105 consid. 2.2.1 p. 107; 134 II 201 consid. 2.2.2 p. 204; 134 I 92 consid. 2.3.2 p. 97), étant précisé que plus la détention se prolonge, plus les exigences relatives à la proportionnalité sont accrues (MINH SON NGUYEN, Les renvois et leur exécution en droit suisse, in Les renvois et leur exécution, Berne 2011, p. 115 ss, 183). Le refus explicite de collaborer de la personne concernée est un indice important, mais d'autres éléments entrent aussi en compte (ATF 135 II 105 consid. 2.2.2 p. 108; 134 II 201 consid. 2.2.4 p. 205 s confirmé notamment in arrêt 2C_538/2010 du 19 juillet 2010 consid. 4.3.1). Ainsi, le comportement de l'intéressé, la possibilité qui lui est offerte de mettre concrètement lui-même fin à sa détention s'il coopère, ses relations familiales ou le fait qu'en raison de son âge, son état de santé ou son sexe, il mérite une protection particulière, peuvent aussi jouer un rôle (arrêts 2C_624/2011 du 12 septembre 2011 consid. 2.1; 2C_936/2010 du 24 décembre 2010 consid. 1.3).
3.2 En l'espèce, le recourant, bien que sous le coup d'une décision d'interdiction d'entrée depuis le 26 août 2008, n'a pas quitté la Suisse et a commis de nombreuses infractions. D'avril 2008 à septembre 2010, il a été condamné à huit reprises, la dernière fois à une peine privative de liberté de huit mois. La décision de renvoi prononcée le 20 mars 2009 à son encontre par l'Office cantonal est entrée en force. Placé en détention administrative depuis 18 avril 2011, le recourant a refusé d'embarquer dans un vol ordinaire à destination d'Alger, le 28 avril 2011. Il a alors été placé, le 17 mai 2011, en détention pour insoumission, décision contre laquelle il a recouru en vain jusqu'au Tribunal fédéral, qui a déclaré son recours irrecevable le 21 juillet 2011. Le même jour, le recourant a de nouveau refusé de monter dans l'avion qui devait le rapatrier dans son pays d'origine. Dans ces circonstances, on ne voit pas quelle mesure moins contraignante que le maintien de sa détention pour insoumission pourrait permettre son renvoi en Algérie. En effet, seuls les renvois volontaires vers ce pays, par vols réguliers, sont actuellement possibles, en application de l'article 4 de l'Accord conclu le 3 juin 2006 entre le Conseil fédéral et le Gouvernement de la République algérienne sur la circulation des personnes (RS 0.142.111.279), les pourparlers que mène la Suisse pour permettre les renvois forcés avec les autorités algériennes n'ayant pour l'instant pas abouti (cf. à ce sujet, question du Conseiller national Dominique Baettig du 13 décembre 2010 et la réponse du même jour du Conseil fédéral publiées sous www.parlement.ch; objets parlementaires; réf.10.5600). La détention pour insoumission du recourant remplit donc les conditions de l'art. 78 al. 1 LEtr.
3.3 La détention administrative du recourant a débuté le 18 avril 2011, de sorte que la prolongation en cause ici, qui implique une détention pour insoumission jusqu'au 8 octobre 2011, reste encore dans le délai de six mois prévu à l'art. 79 al. 1 LEtr.
3.4 Enfin, la décision de prolonger la détention pour insoumission de deux mois ne viole pas la proportionnalité, quoi qu'en dise le recourant, compte tenu de l'ensemble des circonstances. Aux éléments qui viennent d'être énumérés (cf. supra consid. 3.2), s'ajoute le fait que l'intéressé n'a pas de relations familiales particulières dans notre pays, qu'il est jeune et ne fait pas état de problèmes de santé. En outre, il lui suffirait d'accepter de monter dans un vol régulier à destination de l'Algérie pour mettre fin à la mesure de contrainte. Le fait qu'il ait déclaré en mai 2011 qu'il préférait passer 24 mois en détention plutôt que de rentrer en Algérie ne suffit pas à qualifier son maintien en détention pour insoumission qui a commencé le 17 mai 2011 de disproportionné, attendu que le but de cette mesure de contrainte est précisément de modifier son comportement, afin qu'il accepte un retour dans son pays. Par conséquent, la mesure apparaît en l'état comme appropriée et nécessaire.
4. Le recourant invoque une violation de l'art. 80 al. 6 let. a LEtr, au motif que les vols spéciaux à destination de la République algérienne ne sont pas autorisés, de sorte que son renvoi est exclu en pratique, puisqu'il refuse de quitter la Suisse.
4.1 L'article 80 al. 6 let. a LEtr prévoit que la détention est levée notamment lorsque l'exécution du renvoi ou de l'expulsion s'avère impossible pour des raisons juridiques ou matérielles. Sur la base de l'art. 80 al. 6 let. a, la jurisprudence a admis la levée de la détention de Nigérians détenus en vue de leur renvoi au sens de l'art. 76 LEtr, au motif que les vols spéciaux à destination du Nigéria avaient été supprimés, sans qu'il n'y ait aucun indice de reprise de tels vols dans un délai prévisible (arrêts 2C_538/2010 du 19 juillet 2010 consid. 3; 2C_386/2010 du 1er juin 2010 consid. 5 et 2C_473/2010 du 25 juin 2010 consid. 4.2 et les références).
Le recourant, qui se prévaut de la jurisprudence précitée, perd toutefois de vue que ces affaires concernaient des détentions en vue du renvoi, alors qu'il est lui-même détenu pour insoumission (art. 78 LEtr). Or, contrairement à l'objectif de la détention en vue du renvoi, qui est de permettre l'exécution du renvoi de l'étranger en évitant qu'il disparaisse dans la clandestinité (cf. art. 76 LEtr), la détention pour insoumission vise à obtenir un changement de comportement de la personne concernée et ne se justifie que si sa détention en vue du renvoi n'est plus possible sans sa coopération (cf. art. 78 LEtr; arrêt 2C_538/2010 du 19 juillet 2010 consid. 4.3.2; THOMAS HUGI YAR, Zwangsmassnahmen im Ausländerrecht, Ausländerrecht, Bâle 2009, § 10 p. 460 et 481). C'est du reste pour tenir compte de cette différence que l'art. 78 al. 6 let. a LEtr prévoit, par opposition à l'art. 80 al. 6 let. a LEtr (cf. NGUYEN, op. cit., p. 189), que la détention pour insoumission est levée si un départ de Suisse volontaire et dans les délais prescrits n'est pas possible, bien que l'étranger se soit soumis à l'obligation de collaborer avec les autorités. En d'autres termes, tant que l'impossibilité du renvoi dépend de la volonté de l'étranger de collaborer avec les autorités, celui-ci ne peut pas se prévaloir de l'art. 80 al. 6 let. a LEtr en cas de détention pour insoumission. Il ne peut faire valoir l'impossibilité du renvoi pour justifier sa libération que si cette situation n'est pas en lien avec son obligation de collaborer en application de l'art. 78 al. 6 let. a LEtr. Certes, pour l'instant, les vols spéciaux à destination de l'Algérie sont exclus, malgré les pourparlers que mène la Suisse avec cet Etat (cf. supra consid. 3.2). Il n'en demeure pas moins que le recourant peut parfaitement être renvoyé en Algérie s'il coopère. Comme l'impossibilité du renvoi dont il se prévaut dépend de son propre comportement, cette situation ne saurait justifier la levée de sa détention pour insoumission.
5. Le recourant se prévaut aussi d'une violation de l'art. 5 par. 1 CEDH. Il soutient que sa détention ne peut se fonder ni sur la let. b ni sur la let. f de cette disposition. Selon lui, son renvoi ne fait pas l'objet d'une ordonnance rendue par un tribunal et il n'existe aucune obligation prescrite par la loi dont il conviendrait de garantir l'exécution; sa détention ne serait donc pas légitime sous l'angle de l'art. 5 par. 1 let. b CEDH et serait au surplus disproportionnée. En outre, comme son renvoi sur une base volontaire est impossible, aucune procédure d'expulsion ne peut être considérée comme en cours, de sorte que la let. f de l'art. 5 par. 1 CEDH ne lui serait pas non plus opposable.
5.1 Selon l'ATF 135 II 105 consid. 2.2.1 p. 107 (confirmé in arrêt 2C_936/2010 du 24 décembre 2010 consid. 1.2), la privation de liberté découlant d'une décision pour insoumission repose sur l'art. 5 par. 1 let. f CEDH (détention d'une personne contre laquelle une procédure de renvoi en cours) et sert dans ce cadre à garantir l'exécution d'une obligation prescrite par la loi au sens de l'art. 5 ch. 1 let. b CEDH. Elle suppose qu'une procédure de renvoi soit en cours et n'est admissible que si elle a pour but d'assurer l'exécution du renvoi; en outre, elle peut être ordonnée seulement si la personne concernée n'a pas respecté son devoir de quitter le pays volontairement dans le délai fixé (ATF 134 I 92 consid. 2.3.1 p. 96). Il faut encore, sous l'angle de la CEDH également, que la détention pour insoumission paraisse proportionnée, ce qui suppose de tenir compte de l'ensemble des circonstances (ATF 134 I 94 consid. 2.3.2 p. 97; 133 II 97 consid. 2.2 p. 99 s.).
5.2 En l'occurrence, le recourant a fait l'objet d'une interdiction d'entrée prononcée le 26 août 2006 et d'une décision de renvoi le 20 mars 2009. En dépit de ces décisions, il est resté en Suisse et a toujours affirmé s'opposer à un retour en Algérie. A deux reprises, les 28 avril et 21 juillet 2011, les autorités ont organisé son renvoi par vol normal à direction d'Alger, mais il a refusé de monter dans l'avion. Par ailleurs, comme déjà indiqué, la mesure respecte le principe de la proportionnalité (cf. supra consid. 3.4). La prolongation de la détention pour insoumission du recourant jusqu'au 8 octobre 2011 apparaît ainsi comme une restriction à sa liberté admissible et en l'état actuel proportionnée en regard de l'art. 5 par. 1 let. b et f CEDH.
5.3 La position du recourant, qui se prévaut de l'impossibilité de son renvoi sous l'angle de l'art. 5 ch. 1 let. f CEDH, est manifestement infondée. En effet, la détention pour insoumission suppose précisément que le renvoi ne soit pas possible sans la collaboration de l'étranger concerné, ce qui est le cas en l'espèce. On ne peut donc en déduire que la condition que la procédure tendant à son renvoi soit en cours ne serait plus remplie. A suivre un tel raisonnement, un étranger sous le coup d'un renvoi qui refuse de collaborer et rend lui-même son renvoi impossible en raison de son propre comportement ne pourrait être détenu. Ce n'est à l'évidence pas le sens de l'art. 5 par. 1 let. f CEDH en relation avec l'art. 5 par. 1 let. b CEDH, qui autorisent précisément une détention en vue de garantir un renvoi de l'étranger qui se refuse à obtempérer (arrêt 2C_624/2011 du 12 septembre 2011 consid. 4.2.3).
Quant aux développements du recourant tendant à démontrer qu'aucune obligation prescrite par la loi ne lui impose de quitter la Suisse, comme l'exige l'art. 5 par. 1 let. b CEDH, ils s'épuisent en un raisonnement inconsistant revenant à jouer sur les mots. En effet, les art. 64 ss LEtr, consacrés aux mesures d'éloignement, prévoient plusieurs dispositions permettant le renvoi de Suisse et il tombe sous le sens qu'un étranger qui a fait l'objet d'une décision de renvoi entrée en force a l'obligation légale de quitter la Suisse, même si, sous réserve de l'art. 65 al. 1 LEtr, le texte de la loi ne le précise pas expressément. On ne voit pas que la jurisprudence de la CourEDH citée par le recourant (cf. arrêt Engel du 8 juin 1976, Serie A vol. 22 par. 69) et confirmée d'ailleurs par le Tribunal fédéral (cf. ATF 137 I 31 consid. 7.4 p. 51 s.) exclue cette conclusion. La pratique souligne que l'art. 5 par. 1 let. b CEDH ne doit pas être considéré comme une clause générale permettant de mettre en détention toute personne qui contreviendrait de manière générale à l'ordre et à la tranquillité publics; cette norme tend à mettre des limites pour empêcher les privations de liberté abusives; il est ainsi nécessaire que les règles légales dont la détention sert à assurer l'exécution soient suffisamment précises, concrètes et que leur portée ainsi que leur contenu soient clairement saisissables (ATF 137 I 31 consid. 7.4 p. 51 s. et les référence). On ne voit pas qu'une mesure d'éloignement au sens des articles 64 ss LEtr ne remplirait pas ces exigences (arrêt 2C_624/2011 du 12 septembre 2011 consid. 4.2.3).
Comme le Tribunal fédéral l'a déjà indiqué dans l'arrêt 2C_624/2011 précité (loc. cit in fine), la position développée par le recourant revient du reste à remettre en cause la jurisprudence récente qui a admis comme des mesures servant à garantir l'exécution d'une obligation prescrite par la loi au sens de l'art. 5 § 1 lit. b CEDH les détentions pour insoumission prononcées contre des étrangers n'ayant pas obtempéré à une injonction de quitter la Suisse dans le délai prescrit tandis que leur renvoi ne paraît (plus) possible sans leur collaboration (ATF 135 II 105 consid. 2.2.1 p. 107; 134 I 92 consid. 2.3.1 p. 96). Or, aucun motif pertinent ne justifie de s'écarter de cette jurisprudence récente (cf. sur les conditions justifiant une modification de la jurisprudence, ATF 136 III 6 consid. 3 p. 8 et les références).
6. Il résulte de ce qui précède que le recours doit être rejeté. Comme son recours paraissait d'emblée dénué de chances de succès, le recourant ne saurait bénéficier de l'assistance judiciaire (cf. art. 64 LTF). Il ne sera pas alloué de dépens (cf. art. 68 LTF).
Au vu des circonstances de la cause, il se justifie toutefois de ne pas percevoir de frais pour la procédure fédérale (cf. art. 66 al. 1 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est rejetée.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué au mandataire du recourant, au Tribunal administratif de première instance, à la Cour de justice (Chambre administrative) et à l'Office cantonal de la population du canton de Genève, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 16 septembre 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Addy