Faits:
A. Emrah Emre, ressortissant turc né le 18 décembre 1980, est entré en Suisse avec ses parents le 21 septembre 1986. Le 1er juin 1990, il a obtenu une autorisation de séjour annuelle qui a par la suite été régulièrement prolongée.
Les 12 novembre 1997, 10 novembre 1999 et 13 août 2002, Emrah Emre a été condamné à des peines respectivement de deux mois et demi de détention avec sursis, six mois de détention avec sursis et cinq mois d'emprisonnement ferme pour une série d'infractions commises entre 1994 et 2000 (lésions corporelles simples et graves; voies de fait; vol; brigandage; dommages à la propriété; recel; injures; menaces; émeute; violation de la législation sur les armes et violation grave des règles sur la circulation routière).
Par décision du 2 juin 2003, le Service des étrangers du canton de Neuchâtel a prononcé l'expulsion administrative de Emrah Emre pour une durée indéterminée.
Les recours formés par Emrah Emre contre son expulsion ont été rejetés, d'abord le 12 décembre 2003 par le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif), puis le 3 mai 2004 par le Tribunal fédéral, dans un arrêt 2A.51/2004. En résumé, il ressort de ce dernier prononcé que la nécessité de préserver la Suisse d'un délinquant récidiviste, incapable de s'adapter à l'ordre établi et représentant une menace grave pour la sécurité publique, l'emportait, dans la pesée des intérêts, sur l'atteinte à la vie privée et familiale de l'intéressé consécutive à son renvoi dans son pays d'origine.
B. Le 20 octobre 2004, Emrah Emre a été renvoyé en Turquie.
Revenu illégalement en Suisse en mai ou juin 2005, il a été arrêté et placé en détention le 1er juillet 2005 en exécution des mandats d'arrêt émis sur la base de ses condamnations pénales. Après différentes péripéties de procédure ainsi que deux nouvelles condamnations pénales à des peines de trois et deux mois d'emprisonnement respectivement pour utilisation abusive d'une installation de communication et pour rupture de ban, il a apparemment derechef été renvoyé en Turquie le 1er novembre 2005.
C. Entre-temps, le 20 novembre 2004, Emrah Emre avait saisi la Cour européenne des droits de l'homme (ci-après: la Cour européenne) d'une requête tendant à faire constater que son expulsion du territoire suisse pour une durée indéterminée, confirmée par le Tribunal fédéral, violait les art. 3 et 8 de la Convention européenne du 4 novembre 1950 de sauvegarde des droits de l'homme et des libertés fondamentales (CEDH, ci-après également citée: Convention européenne; RS 0.101).
Par arrêt du 22 mai 2008, devenu définitif le 22 août suivant, la Cour européenne a partiellement admis la requête dont elle était saisie, en ce sens qu'elle a constaté que la mesure d'expulsion litigieuse constituait une violation de l'art. 8 CEDH. Elle a de ce chef condamné la Confédération suisse à verser au requérant les sommes de 3'000 EUR à titre de tort moral et de 4'650 EUR pour ses frais et dépens "devant les instances internes et devant la Cour".
Interpellé sur la suite qu'il entendait donner à cette affaire, le Service des migrations du canton de Neuchâtel (ci-après: le Service cantonal) a invité Emrah Emre, le 19 juin 2008, à déposer une demande de révision auprès du Tribunal fédéral.
Par écriture remise à la Poste le 19 novembre 2008, Emrah Emre a formé une demande de révision au Tribunal fédéral, en concluant à l'annulation de son arrêt (précité) 2A.51/2004 du 3 mai 2004, ainsi qu'à l'annulation de l'arrêt précédemment rendu dans cette même affaire par le Tribunal administratif le 12 décembre 2003. Il requiert également le bénéfice de l'assistance judiciaire complète et la désignation de son mandataire comme avocat d'office.
Le Tribunal administratif et le Département de l'économie du canton de Neuchâtel ont renoncé à déposer des observations sur la demande de révision. L'Office fédéral des migrations en propose le rejet.

Considérant en droit:
1. La demande de révision ayant été introduite après l'entrée en vigueur, le 1er janvier 2007 (RO 2006 p. 1242), de la loi du 17 juin 2005 sur le
Tribunal fédéral (LTF; RS 173.110), la procédure est régie par le nouveau droit (<ref-law>; <ref-ruling> consid. 1 p. 47).
2. En vertu de l'<ref-law>, la révision d'un arrêt du Tribunal fédéral pour violation de la CEDH peut être demandée si la Cour européenne a constaté, par un arrêt définitif, une violation de la CEDH ou de ses protocoles. En pareil cas, la demande de révision doit être déposée devant le Tribunal fédéral au plus tard 90 jours après que l'arrêt de la Cour européenne est devenu définitif au sens de l'art. 44 CEDH (art. 124 al. 1 let. c LTF). En outre, le requérant doit avoir la qualité pour former une demande de révision et, notamment, disposer d'un intérêt actuel à obtenir un nouveau jugement sur le point litigieux (cf. arrêt 1F_1/2007 du 30 juillet 2007, consid. 3.3, 3ème paragraphe).
Partie à la procédure ayant abouti à l'arrêt du Tribunal fédéral dont la révision est demandée, le requérant, qui est toujours sous le coup de l'expulsion litigieuse, bénéficie sans conteste de la qualité pour agir et d'un intérêt actuel à obtenir la levée de cette mesure. Par ailleurs, selon les pièces au dossier, l'arrêt de la Cour européenne concerné est devenu définitif le 22 août 2008, si bien que la requête, postée le 19 novembre 2008, a été introduite en temps utile. Cette dernière indique en outre le motif de révision et en quoi consiste la modification de l'arrêt demandée, de sorte qu'il convient d'entrer en matière sur le fond.
3. 3.1 Le motif de révision de l'<ref-law> suppose, outre qu'une requête individuelle ait, comme en l'espèce, été admise pour la violation d'un droit garanti par la CEDH (let. a), qu'une indemnité ne soit pas de nature à remédier aux effets de la violation (let. b) et que la révision soit nécessaire pour remédier aux effets de la violation (let. c). Les conditions posées par cette disposition pour justifier la révision sont analogues à celles qui prévalaient sous l'empire de la loi fédérale d'organisation judiciaire (art. 139a OJ), de sorte que la jurisprudence rendue en application de l'ancien droit conserve en principe toute sa valeur (cf. arrêts 5F_6/2008 du 18 juillet 2008, consid. 2 et 1F_1/2007 du 30 juillet 2007, consid. 3).
3.2 Dans l'arrêt du 22 mai 2008, la Cour européenne a constaté qu'en expulsant Emrah Emre de son territoire pour une durée indéterminée, la Suisse avait violé le droit au respect de la vie privée et familiale de l'intéressé garanti à l'art. 8 CEDH. Elle lui a de ce chef octroyé une indemnité pour tort moral d'un montant de 3'000 EUR sur la base de l'art. 41 CEDH. Cette disposition confère à la Cour européenne la compétence d'accorder une "satisfaction équitable" à la partie lésée lorsque le droit interne de l'Etat mis en cause "ne permet d'effacer qu'imparfaitement les conséquence de [la] violation [constatée]". Le versement d'une telle indemnité ne libère toutefois pas forcément l'Etat concerné de son obligation, prévue à l'art. 46 CEDH, de se conformer aux arrêts de la Cour européenne. L'Etat défendeur, reconnu responsable d'une violation de la Convention ou de ses Protocoles, est en effet appelé non seulement à verser aux intéressés les sommes allouées à titre de satisfaction équitable, mais aussi à choisir, sous le contrôle du Comité des Ministres, les mesures générales et/ou, le cas échéant, individuelles à adopter dans son ordre juridique interne, afin de mettre un terme à la violation constatée par la Cour et d'en effacer autant que possible les conséquences, l'objectif étant de replacer le requérant dans la situation dans laquelle il se trouverait s'il n'y avait pas eu manquement aux exigences de la Convention européenne (cf., parmi d'autres références, arrêt CourEDH du 4 octobre 2007, aff. Verein gegen Tierfabriken Schweiz (VGT) c. Suisse, requête no 32772/02, par. 46 et 47 et les nombreux arrêts cités). C'est le principe de la restitutio in integrum qui a pour effet pratique de limiter la liberté des Etats dans le choix des moyens à mettre en oeuvre pour remédier à une violation de la Convention (cf. MAYA HERTIG RANDALL/ XAVIER-BAPTISTE RUEDIN, L'exécution des arrêts de la Cour européenne des droits de l'homme à la lumière de l'arrêt Vertein gegen Tierfabriken Schweiz (VGT) c. Suisse du 4 octobre 2007, in PJA 2008, p. 651 ss, p. 659).
Dans le cas particulier, la Cour européenne n'a pas prescrit de mesures individuelles en faveur du requérant, excepté le tort moral qu'elle lui a alloué. Or, pas plus cette indemnité que le constat de la violation de l'art. 8 CEDH n'ont pour effet de replacer l'intéressé dans la situation antérieure à l'expulsion de durée indéterminée prononcée contre lui. Il faut donc admettre que la demande de révision réalise la condition prévue à l'<ref-law>, une indemnité, quelle qu'en soit la nature ou l'étendue, n'apparaissant pas de nature à remédier aux effets de la violation constatée. Celle-ci perdurera en effet aussi longtemps que l'intéressé demeurera frappé de la mesure d'expulsion litigieuse, le Service cantonal ayant refusé d'entrer en matière sur sa demande de "reconsidération", en estimant qu'il n'y avait "aucune place" pour une telle procédure au niveau cantonal. A cet égard, la présente cause n'est ainsi pas comparable à l'arrêt 2A.363/2003 où, saisi d'une requête de révision à la suite d'un arrêt de la Cour européenne constatant une violation de l'art. 8 CEDH, le Tribunal fédéral l'avait rejetée, au motif que les autorités compétentes avaient entre-temps levé l'interdiction d'entrée en Suisse et assuré au requérant qu'elles lui accorderaient une autorisation de séjour au titre du regroupement familial dès qu'il en ferait formellement la demande. Dans cette mesure, la demande de révision doit être considérée comme nécessaire pour remédier aux effets de la violation au sens de l'art. 122 let. c LTF .
3.3 Par conséquent, il y a lieu, conformément à l'<ref-law>, d'admettre la demande de révision, d'annuler l'arrêt qui fait l'objet de la demande (2A.51/2004 du 3 mai 2004) et de statuer à nouveau.
4. 4.1 Lorsque, comme en l'espèce, le Tribunal fédéral admet une demande de révision, il rend successivement deux décisions distinctes, même s'il le fait en règle générale dans un seul arrêt. Par la première, dénommée le rescindant, il annule l'arrêt formant l'objet de la demande de révision; par la seconde, appelée le rescisoire, il statue sur le recours dont il avait été précédemment saisi. La décision d'annulation met fin à la procédure de révision proprement dite et entraîne la réouverture de la procédure antérieure. Elle sortit un effet ex tunc, si bien que le Tribunal fédéral et les parties sont replacés dans la situation où ils se trouvaient au moment où l'arrêt annulé a été rendu, la cause devant être tranchée comme si cet arrêt n'avait jamais existé (cf. arrêt précité 1F_1/2007 du 30 juillet 2007, consid. 3.3).
4.2 Dans son arrêt, la Cour européenne a estimé qu'au vu des circonstances, et compte tenu en particulier de la gravité relative des condamnations prononcées contre le requérant, de la faiblesse des liens que celui-ci entretenait avec son pays d'origine, et du caractère définitif de la mesure d'expulsion, la Suisse n'avait pas ménagé un juste équilibre entre les intérêts (privés et public) en présence (arrêt précité, par. 86). Elle a de manière spécifique souligné que la durée indéterminée de l'expulsion était "particulièrement rigoureuse", en considérant que la possibilité pour le requérant d'en obtenir la levée temporaire ou définitive restait à l'heure actuelle "purement spéculative" (arrêt, par. 85). En d'autres termes, elle ne s'en est pas tant prise au principe de la mesure litigieuse, qu'à son caractère définitif. D'une manière générale, dans ses arrêts les plus récents, la Cour européenne semble du reste accorder un poids de plus en plus déterminant à ce dernier critère, se refusant, sous réserve de rares exceptions, à avaliser des expulsions définitives du territoire, au contraire de mesures d'interdiction de durée limitée (cf. CÉDRIC RAUX, Les mesures d'éloi- gnement du territoire devant la Grande chambre de la Cour européenne des droits de l'homme, in: RTDH 2007, p. 837 ss, spécial. p. 843 et les nombreux arrêts cités).
Cela étant, au vu des circonstances qui prévalaient au moment déterminant, soit lorsque l'arrêt annulé a été rendu (le 3 mai 2004), une levée immédiate de l'expulsion n'entrait pas en ligne de compte. Certes les liens du requérant avec la Turquie étaient-ils alors moindres que ceux qu'il avait noués avec la Suisse, de sorte qu'un retour dans son pays d'origine apparaissait comme une mesure relativement rigoureuse pour lui. Cet obstacle avait du reste été pris en considération et discuté dans le premier arrêt. Mais le Tribunal fédéral avait aussi constaté, sans être contredit par la Cour européenne sur ce point, que la présence du requérant en Suisse constituait un danger particulièrement sérieux pour l'ordre et la sécurité publics, car son comportement et ses infractions témoignaient d'un "esprit difficilement capable de résoudre les conflits et les frustrations autrement que par la violence, prêt à faire régner sa propre loi, seul ou à l'aide d'acolytes, méprisant les biens ou l'intégrité corporelle d'autrui, et se moquant ouvertement de l'autorité judiciaire" (arrêt précité du 3 mai 2004, consid. 3.2). Par ailleurs, le Tribunal fédéral avait également souligné, et rien non plus dans l'arrêt de la Cour européenne ne permet de se départir de cette appréciation, que l'intéressé n'avait nullement pris conscience de la gravité de ses actes et qu'il présentait alors un risque élevé de récidive: il avait en effet commis de nouvelles infractions après ses premières condamnations et avait refusé de suivre un traitement psychiatrique pendant sa détention (cf. arrêt précité du Tribunal fédéral du 3 mai 2004, consid. 3.3 in initio). Dans ces conditions, l'intérêt privé du requérant à demeurer en Suisse ne pouvait en aucun cas, compte tenu de son statut de personne adulte, célibataire et sans enfants, l'emporter sur l'intérêt public à son éloignement, au moins pour une période déterminée. En d'autres termes, la seule solution appropriée pour tempérer les effets de la mesure litigieuse prise contre l'intéressé et se conformer à l'arrêt de la Cour européenne des droits de l'homme, consiste à limiter la durée de l'expulsion.
4.3 En conséquence, il se justifie de limiter l'expulsion prononcée contre le requérant à une durée de dix ans à compter de la décision d'expulsion du 2 juin 2003. Passé ce délai, l'intéressé pourra déposer une demande d'autorisation de séjour qui sera examinée par l'autorité compétente à la lumière du droit applicable et des circonstances qui prévaudront alors (situation familiale et personnelle du requérant; comportement de celui-ci depuis son expulsion; etc.).
5. Il suit de ce qui précède que la demande de révision doit être admise et l'arrêt du Tribunal fédéral du 3 mai 2004 annulé. Par ailleurs, l'arrêt rendu le 12 décembre 2003 par le Tribunal administratif doit être réformé, en ce sens la mesure d'expulsion du territoire suisse de durée indéterminée prononcée contre le requérant est remplacée par une mesure d'expulsion d'une durée de dix ans à compter du 2 juin 2003.
6. Comme le requérant a eu gain de cause dans la présente procédure de révision, aucuns frais judiciaires n'est mis à sa charge (<ref-law>). S'étant abstenu de prendre des conclusions, le canton de Neuchâtel ne sera pas tenu à verser des dépens au requérant (<ref-law>) et ceux-ci seront supportés par la Caisse du Tribunal fédéral au titre de l'assistance judiciaire, qu'il convient d'admettre. Me Christophe Tafelmacher, avocat à Lausanne, est désigné comme défenseur d'office (<ref-law>), et une indemnité appropriée au travail nécessité par le recours - limité à une brève écriture - lui est octroyée (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. La demande de révision est admise et l'arrêt du Tribunal fédéral du 3 mai 2004 (2A.51/2004) est annulé.
2. L'arrêt du Tribunal administratif du canton de Neuchâtel du 12 décembre 2003 est réformé en ce sens que Emrah Emre est expulsé du territoire suisse pour une durée de dix ans, avec effet au 2 juin 2003.
3. La demande d'assistance judiciaire est admise.
4. Me Christophe Tafelmacher, avocat à Lausanne, est désigné comme avocat d'office du requérant et une indemnité de 1'000 fr. à titre d'honoraires lui sera versée par la Caisse du Tribunal fédéral.
5. Il n'est pas perçu de frais judiciaires.
6. Le présent arrêt est communiqué au mandataire du requérant, au Département de l'économie publique et au Tribunal administratif du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 6 juillet 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Addy