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'art. 271 al. 1 ch. 4 LP, 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.