Faits:
A. Le 27 janvier 2010, la Commune de B._ a demandé le séquestre du salaire dépassant le minimum vital réalisé par A._, domicilié en France, auprès de X._ SA; la requérante invoquait une créance de 117'652 fr. à titre d'avances sur pensions alimentaires versées du 1er janvier 1989 au 31 décembre 2007 à C._, mère de D._, puis directement à ce dernier dès sa majorité; cette créance découle d'un jugement contumacial rendu le 11 mai 1988 par le Tribunal du district de Meilen, constatant la paternité de A._ sur l'enfant prénommé et le condamnant à verser des pensions alimentaires. Par ordonnance du 25 janvier suivant, la Présidente du Tribunal civil du district du Locle a autorisé, en application de l'<ref-law>, le séquestre de tout "salaire dépassant le minimum vital de A._ [...] auprès de X._ SA [...]", à concurrence de 117'652 fr. et dispensé la requérante de fournir des sûretés.
B. B.a Statuant le 8 avril 2010 sur l'opposition formée par le débiteur, la présidente du tribunal a confirmé l'ordonnance de séquestre à hauteur de 17'540 fr.70, la créance étant prescrite pour le surplus. Par arrêt du 6 septembre 2010, la Cour de cassation civile du Tribunal cantonal du canton de Neuchâtel a annulé cette ordonnance et renvoyé l'affaire au premier juge en l'invitant à examiner si la procédure en paternité avait été "régulière au regard du droit international" et, par conséquent, si la requérante pouvait obtenir une ordonnance de séquestre sur la base de ce jugement.
B.b Par nouvelle ordonnance du 17 janvier 2011, le Tribunal civil du Tribunal régional des Montagnes et du Val-de-Ruz (selon la nouvelle organisation judiciaire neuchâteloise depuis le 1er janvier 2011) a rejeté l'opposition et confirmé intégralement l'ordonnance de séquestre. Par arrêt du 18 mars 2011 (notifié le 23 mars suivant), l'Autorité de recours en matière civile du Tribunal cantonal du canton de Neuchâtel a rejeté le recours du débiteur séquestré.
C. Par acte du 26 avril 2011, A._ exerce un recours en matière civile au Tribunal fédéral; il conclut à l'annulation de cet arrêt, ainsi qu'à celle du jugement sur opposition, et à l'annulation de l'ordonnance de séquestre; subsidiairement, il demande l'annulation de l'arrêt entrepris, ainsi que celle du jugement sur opposition, et le renvoi de la cause à la juridiction précédente, ou à celle de première instance pour nouvelle décision. Il sollicite en outre le bénéfice de l'assistance judiciaire totale pour la procédure fédérale.
Des observations sur le fond n'ont pas été requises.

Considérant en droit:
1. 1.1 Le recours a été interjeté à temps (<ref-law>) à l'encontre d'une décision finale (<ref-law>) rendue en matière de poursuite pour dettes (<ref-law>) par une autorité cantonale de dernière instance statuant sur recours (<ref-law>); la valeur litigieuse atteint amplement 30'000 fr. (<ref-law>); le recourant, qui a été débouté de ses conclusions par la juridiction précédente, a qualité pour recourir (<ref-law>).
1.2 L'arrêt sur opposition au séquestre rendu par l'autorité judiciaire supérieure (<ref-law>) porte sur des mesures provisionnelles au sens de l'<ref-law> (<ref-ruling> consid. 1.2; arrêt 5A_697/2010 du 11 novembre 2010 consid. 1.2); la partie recourante ne peut donc se plaindre que d'une violation de ses droits constitutionnels. Le Tribunal fédéral n'examine un tel grief que s'il a été invoqué et motivé (<ref-law>), à savoir expressément soulevé et exposé de manière claire et détaillée (<ref-ruling> consid. 3 et les arrêts cités).
1.3 Saisi d'un recours fondé sur l'<ref-law> (cf. supra, consid. 1.2), le Tribunal fédéral ne revoit l'application du droit fédéral que sous l'angle restreint de l'arbitraire (arrêt 5A_697/2010 précité consid. 1.3, avec les citations).
De jurisprudence constante, une décision est arbitraire lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou heurte de manière choquante le sentiment de la justice et de l'équité; il ne suffit pas qu'une autre solution paraisse concevable, voire préférable; pour que cette décision soit censurée, encore faut-il qu'elle se révèle arbitraire, non seulement dans ses motifs, mais aussi dans son résultat (<ref-ruling> consid. 2.4; <ref-ruling> consid. 2.2.2 et les arrêts cités). Le justiciable qui se plaint d'une violation de l'art. 9 Cst. ne saurait se contenter de critiquer la décision attaquée comme il le ferait en instance d'appel, où l'autorité supérieure jouit d'une libre cognition; en particulier, il ne peut se borner à opposer son opinion à celle de l'autorité cantonale, mais doit démontrer par une argumentation précise que cette décision repose sur une application de la loi manifestement insoutenable (<ref-ruling> consid. 3, avec les arrêts cités).
2. C'est à juste titre que la juridiction précédente a admis l'application du nouveau code de procédure civile du 19 décembre 2008, en vigueur depuis le 1er janvier 2011 (CPC; RS 272). Conformément à l'<ref-law>, l'appel n'est pas recevable en matière d'opposition au séquestre; une telle décision n'est susceptible que d'un recours au sens des <ref-law> (JEANDIN, in: Code de procédure civile commenté, 2011, n° 14 ad <ref-law>, avec les citations).
En revanche, dans la mesure où l'autorité précédente a examiné sous l'angle de l'arbitraire l'application du droit fédéral (cf. arrêt attaqué, p. 5 consid. 3), son approche est erronée. En vertu de l'<ref-law>, le recours est ouvert pour violation du droit, mais il n'est pas besoin que cette violation soit manifeste ou arbitraire (JEANDIN, op. cit., n° 2 ad <ref-law> et les citations; HOHL, Procédure civile, t. II, 2e éd., 2010, n° 2453). D'après la jurisprudence, l'autorité qui restreint sa cognition à l'arbitraire, alors qu'elle jouit d'un libre pouvoir d'examen, commet un déni de justice formel (<ref-ruling> consid. 4.1 et les références). Le recourant ne soulève pas un tel grief, de sorte qu'il n'y a pas lieu d'en débattre plus avant (<ref-law>).
3. Le premier juge a admis que le jugement du 11 mai 1988, qui indiquait qu'un courrier avait été délivré en main propre à l'opposant par le biais de l'entraide judiciaire internationale, l'informant de l'existence d'une procédure ouverte contre lui, constituait un moyen de preuve suffisant d'une assignation régulière et d'une information suffisante de ses droits même si ce courrier n'avait pas été produit. La juridiction précédente a considéré que cette appréciation n'était pas arbitraire. Par surcroît, le jugement précité indique encore que l'intéressé a été cité sans succès à deux reprises devant le tribunal et qu'il n'a pas davantage donné suite à une convocation du Tribunal de Grande Instance de Paris, sollicité au titre de l'entraide judiciaire internationale. Or, il n'est pas possible qu'aucune de ces communications n'ait atteint son destinataire, ni que celui-ci "n'ait réagi d'aucune manière à ces sollicitations s'il n'avait pas su ce qu'on lui voulait"; dès lors, il était admissible de partir du principe que le débiteur avait été atteint et renseigné sur la procédure ouverte contre lui et que, s'il n'avait pas procédé, "c'était par choix et en toute connaissance de cause".
3.1 Dans un recours soumis à l'<ref-law>, une rectification ou un complément des constatations de fait n'entre en considération qu'en cas de violation de droits constitutionnels (<ref-ruling> consid. 7.1), ce qu'il incombe à la partie recourante d'établir conformément aux exigences légales (<ref-law>; <ref-ruling> consid. 3). Faute de pareille démonstration, les allégations du recourant quant à la connaissance de sa paternité et à ses relations avec la mère de l'enfant apparaissent irrecevables.
3.2 En vertu de l'<ref-law> - dans sa teneur en vigueur jusqu'au 31 décembre 2010 (RO 2010 5601, 5603) -, cas de séquestre applicable en l'espèce, le créancier d'une dette échue et non garantie par gage peut requérir le séquestre des biens d'un débiteur qui n'habite pas en Suisse, s'il n'y a pas d'autre cas de séquestre, pour autant que la créance ait un lien suffisant avec la Suisse ou qu'elle se fonde, en particulier, sur un jugement exécutoire. Le juge de l'opposition examine prima facie si cette dernière condition est réalisée (STOFFEL, in: Basler Kommentar, SchKG III, 1998, n° 78 ad <ref-law> et les citations).
3.3 Les juridictions cantonales ont examiné la validité de l'assignation à comparaître sous l'angle de l'art. 6 de la Convention de La Haye, du 2 octobre 1973, concernant la reconnaissance et l'exécution de décisions relatives aux obligations alimentaires (RS 0.211.213.02); d'après cette disposition, une décision par défaut n'est reconnue ou déclarée exécutoire que si l'acte introductif d'instance contenant les éléments essentiels de la demande a été notifié ou signifié à la partie défaillante selon le droit de l'Etat d'origine et si, compte tenu des circonstances, cette partie a disposé d'un délai suffisant pour présenter sa défense.
Il ressort du jugement rendu le 11 mai 1988 par le Tribunal du district de Meilen que, par lettre du 27 novembre 1986 remise en main propre le 29 janvier 1987 par la voie de l'entraide judiciaire, le recourant a été invité à désigner "in der Schweiz einen Zustellungsempfänger" (cf. p. 3 ch. I). Ce procédé n'est pas conforme au traité. En effet, celui-ci exige que l'acte notifié contienne "les éléments essentiels de la demande", c'est-à-dire "à tout le moins, l'indication de la prétention alimentaire et le fondement légal de celle-ci"; une "simple citation à comparaître à une date fixée devant une certaine autorité ne saurait suffire" (VERWILGHEN, Rapport, in: Actes et documents de la 12e session, T. IV, Obligations alimentaires, 1975, n° 70 p. 414). Il s'ensuit que l'invitation à élire un domicile de notification s'avère insuffisante. Les critiques du recourant sur ce point apparaissent donc justifiées.
La juridiction précédente ajoute cependant que le "jugement de 1988 précise encore que [le recourant] a été cité sans succès à deux reprises devant le tribunal et qu'il n'a pas davantage donné suite à une convocation du Tribunal de Grande Instance de Paris sollicité au titre de l'entraide internationale" (cf. p. 4 consid. 2). Le recourant ne s'en prend pas d'une manière précise à ces constatations de fait, pas plus qu'il n'établit que lesdites citations n'étaient pas conformes à la convention (<ref-law>); cela étant, la déduction de l'autorité précédente, d'après laquelle l'intéressé a "été atteint et renseigné sur la procédure ouverte contre lui", ne saurait être qualifiée d'arbitraire.
Au demeurant, la Cour de céans a jugé qu'une décision - en l'espèce étrangère - dépourvue d'exequatur constituait un titre pouvant servir de moyen de preuve (arrêt 5A_501/2010 du 20 janvier 2011 consid. 2.3.2, approuvé par MABILLARD, obs. in: RSPC 2011 p. 343). Contrairement à ce que soutient le recourant, il est donc erroné de déduire de l'absence éventuelle d'exequatur en raison d'un vice d'assignation la conclusion que la prétention alléguée à l'appui de la requête de séquestre n'a pas été rendue vraisemblable sous l'angle de l'<ref-law>.
4. 4.1 Après avoir rappelé les conditions posées à l'<ref-law>, l'autorité précédente a considéré que la notion "d'agir en Suisse" doit être comprise d'une manière large et "comprend l'impossibilité de faire exécuter un jugement en raison de l'absence d'un domicile permettant l'introduction d'une poursuite". Dans le cas présent, il importe donc peu qu'un jugement ait pu être rendu en Suisse à l'encontre du recourant, car c'est bien l'aptitude de ce jugement à être exécuté en Suisse qui est rendue impossible en raison de l'absence d'un domicile en Suisse de l'intéressé. Par ailleurs, le recourant n'allègue pas que ce serait par négligence que l'intimée n'aurait pas agi contre lui alors qu'elle pouvait le faire. En conséquence, c'est "sans arbitraire aucun" que le premier juge a retenu que, en vertu de l'<ref-law>, la prescription des prétentions alimentaires fondée sur le jugement de 1988 avait été suspendue à tout le moins jusqu'en 2007, date à laquelle le recourant a pris un emploi en Suisse. Les redevances périodiques, en particulier les contributions d'entretien, se prescrivant par cinq ans, les créances invoquées par l'intimée n'étaient pas prescrites au jour du prononcé de l'ordonnance de séquestre contestée.
4.2 En l'espèce, il est constant que l'intimée procède au bénéfice d'une subrogation (<ref-law>; <ref-ruling> consid. 4b; <ref-ruling> consid. 2.1). Ayant acquis les droits du créancier alimentaire dans la mesure où ils existent, à savoir avec la prescription courante (ATF 60 II 30 consid. 3), l'éventuelle prescription des créances alimentaires lui est également opposable (<ref-ruling>; 76 II 113 consid. 5; 74 II 19 consid. 2; E. BUCHER, Schweizerisches Obligationenrecht, Allgemeiner Teil, 2e éd., 1988, p. 456 n. 59). Ces principes ne sont pas contestés par les parties.
4.3 Aux termes de l'<ref-law>, la prescription ne court point, et, si elle avait commencé à courir, elle est suspendue tant qu'il est impossible de faire valoir la créance devant un tribunal suisse. Le Tribunal fédéral a jugé que cette disposition ne s'applique que lorsque le créancier a été empêché par des circonstances objectives, indépendantes de sa situation personnelle, d'introduire une action en Suisse (<ref-ruling> consid. 1.1, avec les références; arrêt 5C.122/2006 du 6 octobre 2006 consid. 3.2, in: SJ 2007 I 209). Comme le souligne l'autorité précédente, une partie de la doctrine estime que l'expression "agir devant un tribunal suisse" englobe notamment la situation où une créance constatée par jugement ne peut pas être exécutée en Suisse faute d'un for de poursuite (DÄPPEN, in: Basler Kommentar, OR I, 4e éd., 2007, n° 8 ad <ref-law>, avec les citations); récemment, le Tribunal administratif fédéral a évoqué cette controverse, mais sans la résoudre (arrêt A-286/2007 du 23 juillet 2009 consid. 3.2.2 et 3.2.3.2).
Il est vrai que la conception suivie par l'autorité précédente s'écarte de la pratique actuelle du Tribunal fédéral, qui s'en tient à l'impossibilité objective d'intenter une action en Suisse, hypothèse qui n'est pas réalisée (<ref-ruling> consid. 4a; arrêt 5C.122/2006 précité consid. 3.3, où le Tribunal fédéral - contre l'opinion de plusieurs auteurs - a refusé d'appliquer la norme précitée "aux cas dans lesquels le créancier qui est privé de la capacité civile active n'a pas de représentant légal"). Le seul fait de ne pas suivre la jurisprudence fédérale n'est cependant pas en soi constitutif d'arbitraire (cf. parmi plusieurs: arrêts 5P.355/2006 du 8 novembre 2006 consid. 2; 5P.387/2004 du 8 mars 2005 consid. 3.2, avec d'autres citations). Pour le surplus, le recourant ne réfute pas les motifs de la décision attaquée, mais se livre à sa propre analyse de la disposition en cause; appellatoire, le moyen est irrecevable dans cette mesure (<ref-law>; <ref-ruling> consid. 2).
Le Tribunal fédéral a précisé que, lorsque le débiteur est domicilié à l'étranger, on peut exiger du créancier qu'il fasse opérer un séquestre en Suisse, une telle possibilité excluant l'application de l'<ref-law> (<ref-ruling> consid. 4b/bb). Ce n'est toutefois le cas que si (indépendamment des autres conditions de l'<ref-law>) le créancier connaît l'existence de biens du débiteur en Suisse; en l'absence de soupçons concrets, il n'est pas tenu de rechercher s'il existe des droits patrimoniaux susceptibles d'y être séquestrés (<ref-ruling> consid. 2.2 et les références). Or, il ne résulte pas de l'arrêt déféré que l'intimée connaissait l'existence de biens du recourant en Suisse avant que celui-ci n'y trouve un emploi (i.e. en 2007); à défaut d'autres actifs, ce n'est qu'à partir de ce moment qu'il y avait en Suisse un avoir (i.e. le salaire) pouvant être mis sous main de justice au siège du tiers débiteur (i.e. l'employeur) de la créance (<ref-ruling> consid. 3.1; <ref-ruling> consid. 4a et la jurisprudence citée).
5. Dans l'optique étroite de l'<ref-law>, la décision attaquée n'apparaît pas arbitraire, de sorte que le présent recours doit être rejeté dans la mesure de sa recevabilité. Les conclusions du recourant étant vouées à l'insuccès, sa requête d'assistance judiciaire doit être rejetée (<ref-law>), ce qui entraîne sa condamnation aux frais de la procédure fédérale (<ref-law>). L'intimée n'ayant pas été invitée à répondre, elle n'a pas droit à des dépens, sans qu'il faille examiner si elle pourrait par ailleurs s'en voir allouer (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire du recourant est rejetée.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et à l'Autorité de recours en matière civile du Tribunal cantonal du canton de Neuchâtel.
Lausanne, le 27 septembre 2011
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
Le Greffier: Braconi