Faits:
A. Ressortissant cap-verdien né en 1968, X._ est entré en Suisse une première fois le 2 novembre 1993 et a obtenu une autorisation saisonnière en donnant une fausse nationalité. L'intéressé n'ayant pas quitté le pays à l'échéance de la validité de ce permis, le Service de la population et des migrants du canton de Fribourg (ci-après: le Service cantonal) a ordonné son refoulement par décision du 19 juin 1995. La police cantonale a constaté le départ de Suisse de X._ en date du 16 septembre 1995.
Etant, selon ses indications écrites, retourné en Suisse le 8 janvier 1996, X._ a, le 19 février 1996, déposé une demande d'autorisation de séjour dans le but d'épouser une ressortissante suisse; le mariage a été célébré le 14 février 1996. L'intéressé a de ce fait obtenu une autorisation de séjour le 5 mars 1996. L'enfant Y._ est née de cette union le 29 septembre 1996. Les conjoints ont divorcé le 12 décembre 2000. X._ a obtenu un permis d'établissement le 6 septembre 2001.
B. Constatant que X._ présentait des arriérés de pensions alimentaires, des poursuites, des actes de défaut de biens et une dette d'assistance sociale importants et qu'il avait été condamné pénalement à plusieurs reprises, entre le 23 janvier 1995 et le 11 novembre 2008, pour diverses contraventions, le Service cantonal a, par décision du 8 juillet 2008, menacé de révoquer son autorisation d'établissement et de le renvoyer de Suisse s'il ne s'efforçait pas immédiatement de s'intégrer professionnellement et socialement. Un nouvel examen de la situation de X._, effectué en 2010 (état au 20 mai 2010), a révélé que l'intéressé a depuis avril 1999 perçu, de manière irrégulière, une aide sociale mensuelle de 1'750 fr., qui totalisait 143'361 fr., dont 4'696 fr. d'abus d'assistance.
Le 7 juillet 2010, X._ a annoncé au Service cantonal avoir renoncé à l'aide sociale depuis le 1er juillet 2010. Le 3 août 2010, il a été informé que les arriérés de pensions alimentaires dues à sa fille Y._ à raison de 546 fr. par mois s'élevaient à 56'164 fr. En outre, X._ avait pour 6'697 fr. de poursuites en cours et faisait l'objet d'actes de défaut de biens pour 54'682 fr.
Dès le 8 juillet 2010, X._ a repris un travail auprès d'une entreprise de travail temporaire, qu'il a dû interrompre à la suite d'un accident subi le 12 juillet 2010. Il a pu reprendre une mission temporaire dès le 25 novembre 2010.
C. Par décision du 8 novembre 2010, le Service cantonal a révoqué l'autorisation d'établissement de X._ en raison de sa situation financière obérée et lui a octroyé, en remplacement, une autorisation de séjour de type B, tout en le menaçant de ne plus renouveler cette autorisation et de le renvoyer de Suisse en l'absence d'efforts d'intégration. Le recours interjeté contre cette décision a été rejeté par la Ie Cour administrative du Tribunal cantonal du canton de Fribourg (ci-après: le Tribunal cantonal) en date du 17 février 2011.
D. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de dépens, d'annuler l'arrêt du Tribunal cantonal du 22 février 2011. Il requiert également le bénéfice de l'assistance judiciaire.
Le Service cantonal et le Tribunal cantonal se réfèrent aux considérants de l'arrêt attaqué.
Considérant en droit:
1. Comme la procédure de révocation du permis d'établissement en faveur du recourant a été initiée le 26 mai 2010, la présente cause est soumise à la loi fédérale du 16 décembre 2005 sur les étrangers, qui est entrée en vigueur le 1er janvier 2008 (RS 142.20; LEtr; cf. art. 126 al. 1 LEtr; arrêt 2C_478/2010 du 17 novembre 2010 consid. 1).
2. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est cependant recevable contre les décisions révoquant une autorisation d'établissement ou constatant qu'une autorisation de ce type est caduque, parce qu'il existe en principe un droit au renouvellement de cette autorisation (ATF 135 II 1 consid. 1.2.1 p. 4).
Pour le surplus, l'arrêt attaqué est une décision finale (art. 90 LTF), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites (art. 42 LTF) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'art. 89 al. 1 LTF, le recours en matière de droit public est par conséquent recevable.
Dans la mesure où les pièces qui accompagnent le mémoire de recours n'ont pas trait à la requête d'assistance judiciaire et ne ressortent pas déjà de la procédure cantonale, il s'agit de moyens nouveaux irrecevables (art. 99 al. 1 LTF).
En tant qu'elle est tardive (cf. art. 102 al. 1 LTF), la détermination de l'Office fédéral ne pourra pas être prise en considération.
3. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation 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.
En outre, le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF), à moins que ceux-ci n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (ATF 134 V 53 consid. 4.3 p. 62) - ou en violation du droit au sens de l'art. 95 LTF (cf. art. 105 al. 2 LTF). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente (cf. art. 97 al. 1 LTF), il doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'art. 105 al. 2 LTF seraient réalisées. Sinon, il n'est pas possible de tenir compte d'un état de fait divergent de celui qui est contenu dans l'acte attaqué. En particulier, la Cour de céans n'entrera pas en matière sur les critiques de type appellatoire du recourant portant sur l'état de fait ou sur l'appréciation des preuves et se fondera sur les faits ressortant de l'arrêt attaqué (ATF 135 II 313 consid. 5.2.2 p. 322).
4. Le Tribunal cantonal a confirmé la révocation de l'autorisation d'établissement du recourant au motif que ce dernier dépendait durablement et dans une large mesure de l'aide sociale (art. 63 LEtr) et que le risque qu'il retombe à la charge de l'assistance publique subsistait malgré la prise d'un emploi temporaire et sa renonciation à l'aide sociale à la suite du soutien apporté par sa nouvelle compagne. Par ailleurs, le Service cantonal n'avait pas abusé de son pouvoir d'appréciation, dès lors qu'avant la décision de révocation, le recourant avait fait l'objet d'une menace.
5. Sous l'angle de l'arbitraire (pour la notion: ATF 137 I 1 consid. 2.4 p. 5) et de la violation du pouvoir d'appréciation, le recourant se plaint de ce que l'arrêt n'aurait pas tenu compte de sa situation personnelle ni de son degré d'intégration en Suisse, et qu'il se serait uniquement basé sur les faits établis par le Service cantonal.
A tort. En effet, les arguments du recourant s'épuisent en de simples critiques appellatoires et n'indiquent pas en quoi les juges cantonaux auraient constaté (ou omis de constater) ou apprécié les faits et preuves de façon insoutenable ni en quoi ceci aboutirait à un résultat choquant. En particulier, les éléments factuels dont se prévaut le recourant - sans les établir - en relation avec la durée ininterrompue de son séjour en Suisse depuis 1993, reviennent à substituer sa propre version des faits à celle retenue par les juges cantonaux. Ces critiques sont partant irrecevables au regard des art. 97 al. 1 et 106 al. 2 LTF. De plus, il ressort de l'arrêt entrepris, notamment de son état de fait ainsi que des considérations relatives au pouvoir d'appréciation des autorités (art. 96 al. 1 LEtr; arrêt attaqué, p. 6 s.) que le Tribunal cantonal a, contrairement à ce que prétend le recourant, tenu compte de la situation socio-économique, y compris familiale, alléguée par ce dernier.
En tant qu'ils sont recevables, les griefs tirés de l'arbitraire et de l'abus du pouvoir d'appréciation doivent partant être écartés. La Cour de céans se fondera donc exclusivement sur les faits établis par le Tribunal cantonal.
6. Le recourant invoque une violation de l'art. 63 LEtr. Il affirme notamment avoir séjourné en Suisse durant plus de quinze ans, de sorte que son permis d'établissement ne pouvait être révoqué en raison de sa dépendance de l'aide sociale.
6.1 D'après l'art. 63 al. 1 let. c LEtr, l'autorisation d'établissement peut être révoquée lorsqu'un étranger dépend durablement et dans une large mesure de l'aide sociale. Le motif de révocation découlant de la dépendance à l'aide sociale ne s'applique toutefois pas à l'étranger qui séjourne en Suisse légalement et sans interruption depuis plus de quinze ans (art. 63 al. 2 LEtr). Le respect de cette durée se vérifie au jour du prononcé de la décision de révocation de l'autorisation d'établissement par l'autorité de première instance (ATF 137 II 10 consid. 4.2 p. 12). Le séjour de l'étranger en Suisse est légal (en allemand: "ordnungsgemäss"; en italien: "regolar[e]") s'il est autorisé au regard du droit des étrangers, ce qui est admis pour la période entre le mariage de l'étranger conclu en Suisse et l'obtention d'une autorisation de séjour à ce titre. En revanche, lorsque la présence d'un étranger est uniquement tolérée, notamment en raison de l'effet suspensif accordé dans un litige relatif à l'obtention ou au maintien d'un titre de séjour, dans le cadre de l'examen d'une demande d'asile qui sera définitivement rejetée, ou en cas d'inexécution d'un renvoi par l'autorité, le séjour n'est pas considéré comme étant légal au sens de l'art. 63 al. 2 LEtr (ATF 137 II 10 consid. 4.4, 4.6 et 4.7 p. 13 et 15 s.; cf. aussi l'arrêt 2A.105/2001 du 26 juin 2001 consid. 3c).
En l'occurrence, les conditions de l'art. 63 al. 2 LEtr ne sont pas remplies. La décision de révocation de l'autorisation d'établissement adoptée par le Service cantonal date du 8 novembre 2010, si bien que, pour maintenir un séjour légal et ininterrompu en Suisse, le recourant aurait dû y résider au plus tard à partir du 8 novembre 1995. Or, tel que les juges cantonaux l'ont constaté en se fondant sur les déclarations écrites du recourant lui-même (consid. 5), celui-ci est revenu en Suisse en janvier 1996 et ne s'est marié avec une Suissesse qu'en date du 14 février 1996, de sorte qu'il ne peut se prévaloir d'un séjour ininterrompu de quinze ans dans notre pays. Même si l'on prêtait foi à l'affirmation - non étayée - du recourant selon laquelle il n'aurait pas réellement quitté la Suisse en 1995, il ne pourrait se fonder sur ces années supplémentaires au regard de l'art. 63 al. 2 LEtr, dès lors que durant cette période, son séjour en Suisse aurait été illégal en raison de la décision de refoulement prononcée à son encontre en 1995.
6.2 Il convient encore d'examiner si les conditions permettant à l'autorité de révoquer l'autorisation d'établissement en faveur du recourant étaient réunies (art. 63 al. 1 let. c LEtr).
6.2.1 Ce motif de révocation correspond en substance au motif d'expulsion de l'art. 10 al. 1 let. d LSEE, si bien que la jurisprudence rendue au sujet de cette dernière disposition demeure pertinente (cf. FF 2002 3469, p. 3565; MARC SPESCHA, ad art. 63 LEtr, in: Migrationsrecht [Marc Spescha et al. (éds)], 2ème éd., Zurich 2009, p. 155 N 11; ANDREAS ZÜND/LADINA ARQUINT HILL, Beendigung der Anwesenheit, Entfernung und Fernhaltung, in: Ausländerrecht [Peter Uebersax et al. (éds)], Bâle 2009, p. 311 ss, 327).
6.2.2 La notion d'assistance publique (ou d'aide sociale selon la LEtr) doit être interprétée dans un sens technique. Elle comprend l'aide sociale traditionnelle et les revenus minima d'aide sociale, à l'exclusion des prestations d'assurances sociales, comme les indemnités de chômage ou les prestations complémentaires à l'AVS et à l'AI (cf. arrêts 2C_448/2007 du 20 février 2008 consid. 3.4, in: ZBl 110/2009 p. 515; 2C_210/2007 du 5 septembre 2007 consid. 3.1).
6.2.3 Pour apprécier si une personne se trouve dans une large mesure à la charge de l'aide sociale, il faut tenir compte du montant total des prestations déjà versées à ce titre (arrêt 2C_210/2007 précité, consid. 3.1, in: SJ 2008 I 153 & 165). Pour évaluer si elle tombe d'une manière continue à la charge de l'aide sociale, il faut examiner sa situation financière à long terme. Il convient en particulier d'estimer, en se fondant sur la situation financière actuelle de l'intéressé et sur son évolution probable, y compris au regard des capacités financières des membres de sa famille, s'il existe des risques que, par la suite, il se trouve à la charge de l'assistance publique (ATF 122 II 1 consid. 3c p. 8; 119 Ib 1 consid. 3b p. 6; arrêt 2C_448/2007 du 20 février 2008 consid. 3.1, in: ZBl 110/2009 p. 515). Le Tribunal fédéral a jugé que les critères de l'importance et du caractère durable de la dépendance à l'aide sociale étaient, notamment, réunis dans les cas d'une famille de cinq personnes ayant perçu plus de 210'000 fr. d'aide sociale sur une période d'environ onze ans (arrêt 2A.692/2006 du 1er février 2007 consid. 3.2.1); d'un recourant à qui plus de 96'000 fr. avaient été alloués sur neuf années (ATF 123 II 529 consid. 4 p. 533); d'un couple assisté à hauteur de 80'000 fr. sur une durée de cinq ans et demi (ATF 119 Ib 1 consid. 3a p. 6); ou d'un couple ayant obtenu 50'000 fr. en l'espace de deux ans (arrêt 2C_672/2008 du 9 avril 2009 consid. 3.3).
6.2.4 Il ressort de l'arrêt attaqué qu'en date du 20 mai 2010, la dette sociale accumulée, depuis avril 1999, par le recourant vis-à-vis du Service de l'aide sociale de la Ville de Fribourg s'élevait à 143'361 fr., dont 4'696 fr. issus d'un abus d'assistance. Au regard de la jurisprudence du Tribunal fédéral (consid. 6.2.3), une dette sociale d'une telle ampleur, générée par une personne sur une période de douze ans, permet de conclure que l'intéressé dépendait dans une large mesure de l'aide sociale. La question de savoir si les contributions d'entretien de 56'164 fr. que l'Etat a en grande partie (42'782 fr.) avancées en faveur de l'enfant du recourant sont assimilables à des prestations d'aide sociale peut en conséquence rester indécise.
S'agissant du critère de la dépendance durable du recourant à l'aide sociale, l'arrêt litigieux a constaté que depuis la menace de révocation de l'autorisation d'établissement prononcée le 8 juillet 2008, la dette d'aide sociale du recourant était passée de 114'000 fr. à 143'000 fr. Les arriérés de pension alimentaire en faveur de la fille du recourant avaient également augmenté de 16'000 fr. De plus, l'intéressé faisait l'objet de poursuites pour 6'697 fr. et d'actes de défaut de biens à hauteur de 54'692 fr. Au vu de ces dettes importantes, le Tribunal cantonal a estimé que la situation financière du recourant demeurait obérée. En dépit de sa renonciation récente à l'aide sociale, de la reprise, sous la pression de la procédure de révocation, comme retenu par les juges cantonaux, d'un travail temporaire et donc précaire et de l'aide financière que la nouvelle compagne du recourant s'était déclarée disposée à lui fournir, à bien plaire, le risque que ce dernier tombe à nouveau à la charge de l'assistance publique demeurait très vraisemblable.
Compte tenu des éléments constatés sans arbitraire par l'arrêt attaqué, du pouvoir d'appréciation qui doit être reconnu aux autorités à cet égard (cf. ATF 119 Ib 1 consid. 3b p. 6) et du fait que l'amélioration de la situation financière du recourant est encore trop récente et précaire pour pouvoir être qualifiée de stable ou durable (cf. arrêt 2C_761/2009 du 18 mai 2010 consid. 7.2), les juges cantonaux n'ont pas violé le droit en posant un pronostic défavorable quant à l'évolution financière probable de l'intéressé et à la nécessité de faire appel à l'assistance sociale à l'avenir; ils pouvaient ainsi considérer comme durable la dépendance du recourant à l'aide sociale.
Il sera encore précisé que, contrairement à ce que prétend le recourant sur la base d'une interprétation erronée des directives de l'Office fédéral relatives à la LEtr (cf. les Directives n° I [mesures d'éloignement], ch. 8.2.1.5.2 let. d, p. 11, dans leur version actuelle du 1er juillet 2009), la période déterminante pour évaluer si la dépendance à l'aide sociale est durable, n'est pas limitée à deux à trois ans; au contraire, ce nombre d'années constitue en principe la durée minimale (cf. ATF 119 Ib 1 consid. 3b p. 6) à partir de laquelle il peut être admis que l'autorité disposera de suffisamment de recul pour apprécier ou non le caractère durable et important de la dépendance de l'étranger de l'aide sociale.
6.3 Par conséquent, le Tribunal cantonal a, à juste titre, retenu que les conditions légales permettant de révoquer l'autorisation d'établissement dont dispose le recourant étaient réunies, de sorte que le grief tiré de la violation de l'art. 63 LEtr doit être rejeté.
7. Invoquant la durée de sa présence et son intégration en Suisse, notamment sa vie familiale, de même que les efforts récents entrepris pour mettre un terme à sa dépendance de l'aide sociale, le recourant se plaint aussi de la violation du principe de proportionnalité.
7.1 Le principe de la proportionnalité est exprimé de manière générale à l'art. 5 al. 2 Cst. Il exige que la mesure prise par l'autorité soit raisonnable et nécessaire pour atteindre le but d'intérêt public ou privé poursuivi (cf. ATF 136 I 87 consid. 3.2 p. 91 s.). Ce principe découle également de l'art. 96 LEtr relatif au pouvoir d'appréciation dont dispose l'autorité de police des étrangers (cf. ATF 135 II 377 consid. 4.2 p. 380); celle-ci est tenue de faire preuve de beaucoup de retenue dans l'application des révocations d'autorisations d'établissement pour cause de dépendance vis-à-vis de l'aide sociale (cf. FF 2002 3469, p. 3566).
7.2 En l'espèce, les conditions justifiant de révoquer l'autorisation d'établissement du recourant étaient réunies (consid. 6). Or, il ressort de l'arrêt querellé que la menace de révoquer le permis d'établissement prononcée, en date du 8 juillet 2008, par le Service cantonal afin d'inciter l'intéressé à entreprendre immédiatement des efforts notables pour s'intégrer professionnellement et socialement, n'avait pas produit les effets escomptés. Le recourant est demeuré à la charge de l'aide sociale et ne semble avoir consenti des efforts de recherche d'emploi accrus qu'une fois initiée, en date du 26 mai 2010, la procédure de révocation à proprement parler. Pour ce motif déjà, la mesure de révocation du permis d'établissement constituait une mesure non disproportionnée; il ne pouvait de plus être exigé du Service cantonal, au vu de l'inefficacité de la menace du 8 juillet 2008 sur le comportement du recourant, qu'il adoptât préalablement un second avertissement selon l'art. 96 al. 2 LEtr.
Le grief tiré de la violation de la proportionnalité est d'autant moins fondé que le Service cantonal aurait dû se contenter de révoquer l'autorisation d'établissement du recourant, et prononcer son renvoi immédiat de Suisse à la place de le faire bénéficier d'une autorisation de séjour. En effet, lorsque les conditions de révocation d'une autorisation d'établissement sont réalisées, l'autorité ne peut pas envisager l'octroi d'une autorisation de séjour (cf. arrêts 2C_13/2011 du 22 mars 2011 consid. 2.3; 2C_254/2010 du 15 juillet 2010 consid. 4.3; sous l'ancien droit: arrêt 2C_761/2009 du 18 mai 2010 consid. 7.4.2).
En tant que la délivrance d'un tel titre de séjour conduit à ce que le recourant puisse demeurer en Suisse, en lui accordant une ultime chance pour ne plus dépendre de l'aide sociale de notre pays, celui-ci est à l'évidence mal venu de prétendre que l'arrêt attaqué compromettrait ses chances sur le marché du travail ou l'empêcherait de "mener une vie décente auprès de sa copine et de ses enfants".
8. Les considérants qui précèdent conduisent au rejet du recours, dans la mesure où il est recevable. Le recourant a sollicité sa mise au bénéfice de l'assistance judiciaire. Sa cause paraissant dépourvue de chances de succès dès le dépôt du recours (cf. ATF 135 I 1 consid. 7.1 p. 2), la demande d'assistance judiciaire doit être rejetée (art. 64 al. 1 et 2 LTF). Les frais seront mis à la charge du recourant, qui succombe, mais fixés en tenant compte de sa situation financière obérée (art. 65 al. 2 et 3 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 en matière de droit public 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 représentant du recourant, au Service de la population et des migrants du canton de Fribourg, au Tribunal cantonal du canton de Fribourg, Ie Cour administrative, et à l'Office fédéral des migrations.
Lausanne, le 22 juillet 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Chatton