Faits:
A. A.a D._ et ses deux enfants, nés en ... et ..., ont bénéficié de l'aide sociale depuis le 1er septembre 2002. En mai 2003, elle s'est mise en ménage commun avec G._, alors marié et dont elle a eu un enfant né en .... Par lettre du 10 août 2004, l'Office social de la Ville de Neuchâtel a informé les intéressés qu'ils seraient considérés sous l'angle de l'aide sociale comme un couple marié. Dès le mois de septembre 2004 G._ s'est constitué un domicile séparé de celui de sa compagne. Au regard de cette nouvelle situation, D._, ainsi que ses enfants, ont pu continuer à bénéficier d'une aide sociale.
Au mois de mars 2006, G._ a perdu son poste de travail de gendarme et il s'est inscrit au chômage dès le mois d'avril 2006. A partir du mois de mai 2006, il a repris la vie commune avec D._.
Le 15 août 2006, le Tribunal civil du district de La Chaux-de-Fonds a prononcé le divorce des époux G._ et C._ née B._. Il a condamné G._ à verser à l'épouse une contribution mensuelle d'entretien de 1'200 fr. jusqu'au 31 décembre 2018, puis de 700 fr. après cette échéance. L'office cantonal de recouvrement et d'avances des contributions d'entretien a demandé à la caisse de chômage de prélever l'équivalent de la contribution d'entretien de 1'200 fr. sur les indemnités de chômage dues à l'intéressé et de les verser sur le compte dudit office.
G._ est par ailleurs astreint à une contribution d'entretien en faveur d'un enfant né d'un précédent mariage.
A.b Par décision du 11 octobre 2006, l'Office de l'aide sociale de la Ville de Neuchâtel a notifié à D._ et à G._ qu'il supprimerait l'aide allouée dès le 1er août 2006, motif pris qu'ils vivaient en concubinage avec un enfant commun et qu'ils devaient en conséquence être considérés comme un couple marié sous l'angle de l'aide sociale. Leurs revenus cumulés étaient supérieurs au budget d'aide sociale arrêté à 4'286 fr. Il ne pouvait pas être tenu compte des contributions d'entretien versées par G._.
B. D._ et G._ ont recouru contre cette décision. Selon eux, bien qu'ils vécussent en concubinage, seule D._ restait à partir du mois d'août 2006 demanderesse et bénéficiaire de l'aide allouée, à l'exclusion de son partenaire. Celui-ci ne devait donc pas participer à toutes les charges de sa compagne et il convenait, dans la détermination des besoins du couple, de tenir compte des pensions alimentaires versées par G._, ainsi que de sa charge fiscale et d'un prêt qu'il devait rembourser. Le Département de la santé et des affaires sociales (DSAS) du canton de Neuchâtel a rejeté le recours par décision du 12 août 2008.
C. Statuant le 31 mars 2009, le Tribunal administratif du canton de Neuchâtel a rejeté un recours formé contre cette décision par D._ et G._.
D. D._ et G._ interjettent un recours en matière de droit public dans lequel ils concluent à l'annulation du jugement cantonal, assortie du renvoi de la cause à l'autorité intimée pour nouvelle décision. Ils demandent l'assistance judiciaire pour la procédure fédérale.
L'Office de la santé et des affaires sociales de la Ville de Neuchâtel a renoncé à se déterminer. Le DSAS a conclu au rejet du recours.

Considérant en droit:
1. Interjeté par des parties directement touchées par la décision entreprise et qui ont un intérêt digne de protection à son annulation ou sa modification (art. 89 al. 1 LTF), le recours est dirigé contre un jugement final (art. 90 LTF) rendu dans une cause de droit public (art. 82 let. a LTF) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF). Il a été déposé dans le délai (art. 100 al. 1 LTF) et la forme (art. 42 et 106 al. 2 LTF) prévus par la loi et l'on ne se trouve pas dans l'un des cas d'exceptions mentionnés par l'art. 83 LTF. Le recours est donc recevable au regard des dispositions citées.
2. Saisi d'un recours, le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Le recourant ne peut critiquer ceux-ci que s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.3) - ou en violation du droit au sens de l'art. 95 LTF (art. 97 al. 1 LTF), ce qu'il lui appartient d'exposer et de démontrer de manière claire et circonstanciée. La correction du vice doit en outre être susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF).
Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF), sans être lié par les arguments soulevés dans le recours ni par la motivation retenue dans la décision attaquée. Toutefois, eu égard à l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (art. 108 al. 1 let. b LTF), il n'examine en principe que les griefs invoqués. Au demeurant, il ne peut pas entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal si le grief n'a pas été invoqué et motivé de manière précise par la partie recourante (art. 106 al. 2 LTF).
3. Selon l'art. 5 de la loi sur l'action sociale du canton de Neuchâtel du 25 juin 1996 (LASoc; RSN 831.0), une personne est dans le besoin lorsqu'elle éprouve des difficultés matérielles ou sociales ou ne peut subvenir à son entretien, d'une manière suffisante ou à temps, par ses propres moyens. En vertu du principe de subsidiarité applicable en la matière, l'aide sociale matérielle - allouée en espèces ou en nature (cf. art. 4 al. 1 let. b) - est accordée dans la mesure où la personne dans le besoin ne peut faire valoir ou obtenir une prestation découlant d'une obligation d'entretien en application du code civil, de la loi fédérale sur le partenariat enregistré entre personnes du même sexe ou d'autres prestations légales (art. 6 LASoc). L'art. 38 LASoc dispose que le Conseil d'État arrête les normes pour le calcul de l'aide matérielle. L'art. 23 de l'arrêté du Conseil d'État fixant les normes pour le calcul de l'aide matérielle du 4 novembre 1998 (RSN 831.02) précise que le service de l'action sociale émet les directives d'application nécessaires tandis que l'art. 24 dudit arrêté dispose que les concepts et normes pour le calcul de l'aide sociale de la Conférence suisse des institutions d'action sociale (CSIAS) font référence pour le surplus. En outre l'art. 17 de l'arrêté dispose qu'à l'exception de la franchise prévue à l'art. 3b (sur les revenus provenant de l'activité lucrative) l'ensemble des revenus et de la fortune du bénéficiaire sont pris en considération dans le calcul du budget de l'aide matérielle. L'art. 19 prévoit que lorsqu'une personne vit dans le même ménage que le bénéficiaire, le montant du forfait mensuel pour l'entretien est réduit de la part qui la concerne (al. 1). L'autorité d'aide sociale prend en outre en considération sa participation au loyer et aux autres frais communs calculée par tête (al. 2). Lorsque cette personne exerce une activité lucrative, l'autorité d'aide sociale prend en considération une indemnisation pour les services que le bénéficiaire lui rend (al. 3).
4. 4.1 La juridiction cantonale considère que le droit cantonal neuchâtelois ne contient pas de règle de calcul de l'aide sociale matérielle régissant la situation des recourants, soit celle d'un ménage formé de deux concubins avec un enfant commun et d'autres enfants à charge, et dont seul un des partenaires sollicite l'aide de la collectivité. Se référant aux normes CSIAS F.5.1 au titre de droit cantonal supplétif, elle estime admissible de considérer un concubinage comme stable ou qualifié dès qu'un couple avec un enfant fait ménage commun, sans que d'autres conditions soient remplies. En raison des obligations qu'entraîne un concubinage stable et en vertu du principe de subsidiarité applicable en matière d'aide sociale, il n'est pas critiquable d'additionner les revenus des deux concubins pour examiner la prétention à l'aide sociale de la mère et de l'enfant, même si le partenaire de celle-ci ne sollicite pas lui-même une aide matérielle. Considérer simplement ce partenaire comme une personne qui vit dans le même ménage que le bénéficiaire au sens de l'art. 19 de l'arrêté violerait le principe de l'égalité de traitement. Pour ce qui est des contributions alimentaires dues par G._, elles n'ont pas à être prises en compte: selon le Tribunal administratif, il incombe au concubin de faire reconnaître sa véritable situation auprès des tiers auxquels il doit des aliments et des rentes.
4.2 Les recourants admettent que la relation qu'ils entretiennent est une relation de concubinage stable. Ils ne contestent pas le principe selon lequel le revenu du partenaire non bénéficiaire de l'aide sociale doit être pris en compte de manière appropriée pour déterminer si la personne assistée se trouve dans le besoin et nécessite une aide de la collectivité.
Les recourants reprochent en revanche au Tribunal administratif d'avoir écarté de manière arbitraire l'application de l'art. 19 de l'arrêté cantonal fixant les règles de calcul de l'aide matérielle. Sans remettre en cause l'application de principe des normes CSIAS à leur situation, ils soutiennent que les premiers juges les ont méconnues dans le cas concret. Selon eux, ces normes prescrivent en effet de tenir compte des obligations alimentaires que le concubin non bénéficiaire de l'aide matérielle est tenu de verser. Il serait également contraire à ces normes de faire abstraction de la charge fiscale et du remboursement d'un emprunt du concubin. Les recourants invoquent dans ce contexte "l'aide à la pratique" H.10 des normes CSIAS, selon laquelle il faut examiner la capacité financière du partenaire non bénéficiaire d'aide sociale au moyen d'un budget élargi et ce de manière appropriée aux circonstances. Dans un tel budget il serait notamment tenu compte des obligations d'entretien, des impôts courants et du remboursement des dettes. Invoquant par ailleurs la jurisprudence du Tribunal fédéral, les recourants font valoir que l'obligation d'entretien entre époux, fixée dans une procédure de séparation ou de divorce, est prépondérante à toute obligation qui découlerait d'un concubinage du débirentier. De manière plus générale, les recourants reprochent aux premiers juges de ne pas avoir examiné leurs griefs.
5. Le moyen tiré d'une application arbitraire de l'art. 19 de l'arrêté cantonal apparaît d'emblée mal fondé. Comme le relève le DSAS dans sa prise de position, cette disposition concerne des personnes non bénéficiaires de l'aide sociale vivant dans le même ménage que le bénéficiaire de l'aide, comme les membres de la famille ou les concubins non stables. Il s'agit de communautés de résidence ou de vie au sens des normes CSIAS 12/07 F.5-1. Par une telle communauté on entend les partenaires et les groupes qui assument et financent ensemble les fonctions ménagères conventionnelles (gîte, couvert, lessive, entretien, télécommunications, etc.). Ils vivent donc ensemble, sans pour autant constituer formellement un couple stable ou une famille. Cette interprétation, qui se fonde sur les normes CSIAS, ne saurait être taxée d'arbitraire (voir aussi CLAUDIA HÄNZI, Leistungen der Sozialhilfe in den Kantonen, in Das Schweizerische Sozialhilferecht, 2008, p. 148; arrêt 2P.242/2003 du 12 janvier 2004). Cela étant, il y a lieu d'admettre, avec les premiers juges, que la relation de concubinage stable, sous l'angle de l'aide sociale, n'est pas directement réglée par la législation cantonale.
6. 6.1 Si une personne assistée vit dans une relation de concubinage stable, la jurisprudence en matière d'aide sociale admet qu'il n'est pas arbitraire de tenir compte de cette circonstance dans l'évaluation des besoins d'assistance, quand bien même il n'existe pas un devoir légal et réciproque d'entretien entre les partenaires. Dans cette optique, il est admissible de tenir compte du fait que ces derniers sont prêts à s'assurer mutuellement assistance (<ref-ruling> consid. 5.5 p. 318; FamPra.ch 2004 p. 434, 2P.242/2003 du 12 janvier 2004 consid. 2; arrêts 2P.230/2005 du 10 juillet 2006 consid. 3.3, 2P.218/2003 du 12 janvier 2004 consid. 3.2 et 2P.386/1997 du 24 août 1998; CLAUDIA HÄNZI, op. cit., p. 146). Dans ce même ordre d'idées, le Tribunal fédéral a jugé, s'agissant de l'avance de pensions alimentaires, qu'une disposition cantonale selon laquelle les revenus du concubin du parent ayant droit sont pris en compte, et l'avance alimentaire accordée seulement si le revenu total des deux concubins ne dépasse pas la limite fixée, n'était pas arbitraire (<ref-ruling>). Le Tribunal fédéral a transposé cette jurisprudence au domaine des subsides d'assurance-maladie en confirmant la légalité d'une disposition réglementaire cantonale en vertu de laquelle le revenu déterminant d'un concubin doit être calculé en cumulant les revenus des personnes vivant en ménage commun (<ref-ruling>).
6.2 S'agissant d'une relation de concubinage stable, il existe des pratiques cantonales différentes pour la prise en compte des ressources du partenaire non bénéficiaire pour la fixation des besoins de l'autre partenaire. Certains cantons se fondent sur le revenu net de la communauté domestique formée par les concubins; les dettes fiscales sont prises en compte dans l'établissement du budget (voir les jugements, cités par CLAUDIA HÄNZI, [op. cit., p. 147 sv.], du Tribunal administratif du canton de Soleure du 5 septembre 2006 et du Tribunal administratif du canton de Zurich du 13 janvier 2005, in: VB.2004.00419; voir aussi le jugement du 12 décembre 2007, in: VB. 2007.00399). D'autres cantons renoncent à une complète assimilation des concubins aux couples mariés, mais prennent en considération les revenus du concubin (non bénéficiaire) à raison d'un montant jugé approprié (ibidem, à propos de jugements concernant le canton d'Argovie du 28 avril 2005, in AGVE 2005 p. 283 et le canton de Schaffhouse du 1er novembre 2002, 60/2002/4). D'après la jurisprudence du Tribunal fédéral, il n'est pas arbitraire d'additionner les revenus des deux partenaires pour fixer le montant de l'aide sociale de la mère et de leur enfant commun lorsque tous trois forment une communauté domestique (arrêts 2P.218/2003 du 12 janvier 2004 consid. 3.3.2 et 2P.242/2003 du 12 janvier 2004 consid. 2.4). Cela ne signifie cependant pas que les couples mariés et les concubins vivant avec un enfant commun doivent absolument être traités de la même manière sous l'angle de l'aide sociale: une pratique cantonale plus large ou plus restrictive est admissible. Ainsi dans l'arrêt déjà cité 2P.230/2005 du 10 juillet 2006, le Tribunal fédéral a relevé qu'il existe entre le concubinage et le mariage des différences de fait et de droit susceptibles de justifier, dans une certaine mesure tout au moins, des différences de traitement. Cela n'exclut cependant pas que les cantons traitent comme des couples mariés des personnes qui vivent comme une famille dans un concubinage stable avec un enfant commun. Le Tribunal fédéral n'exige toutefois pas que les deux communautés soient traitées de façon identique.
6.3 Globalement, les normes CSIAS vont dans le même sens. Elles prévoient que les personnes vivant en communauté de type familial avec un bénéficiaire ne peuvent en principe pas être considérées comme unités d'assistance et que les concubins bénéficiaires de l'aide sociale ne doivent par ailleurs pas être mieux traités que les couples mariés. Si les partenaires vivent en concubinage stable et si une seule personne est bénéficiaire de l'aide sociale, le revenu et la fortune du partenaire non bénéficiaire peuvent être pris en compte de manière appropriée. Un concubinage est considéré comme stable s'il dure depuis deux ans au moins ou si les partenaires vivent ensemble avec un enfant commun (normes CSIAS 12/07 F.5-2). Dans un concubinage stable, la capacité financière du partenaire non bénéficiaire peut entraîner la suppression du droit à l'aide sociale (normes CSIAS, "aide à la pratique", 12/07 H.10-2 sous let. b).
6.4 Les normes CSIAS tendent à assurer aux bénéficiaires non seulement le minimum vital, soit la couverture des besoins fondamentaux englobant toutes les dépenses courantes nécessaires à l'entretien du ménage, mais aussi le minimum social visant à leur donner la possibilité de participer à la vie active sociale, en favorisant la responsabilité de soi et l'effort personnel (normes CSIAS 04/05 A.1-1; arrêt 2P.325/1995 du 17 janvier 1996 consid. 3c, in RDAF 1998 I p. 448 sv.). Bien qu'elles ne présentent pas le caractère de normes juridiques, elles jouent un rôle important en pratique. Elles constituent des normes de référence adéquates pour la détermination de l'aide sociale qui est nécessaire pour assurer le minimum social. Elles visent à garantir la sécurité juridique et l'égalité de traitement entre justiciables. Elles évitent que les personnes soutenues déplacent leur domicile en fonction de considérations liées aux divergences de réglementations en ce domaine ou que certaines communes tentent de se décharger de leurs obligations en incitant indirectement les personnes assistées à déménager dans des communes réputées plus avantageuses pour les intéressés. Une interprétation du droit cantonal fondée sur ces normes ne saurait donc sans plus être taxée d'arbitraire. Eu égard au principe de l'individualisation de l'aide sociale, elles n'ont cependant pas de portée contraignante (arrêt précité 2P.325/1995 consid. 3; FELIX WOLFFERS, Grundriss des Sozialhilferechts, 2ème éd., 1999, p. 138 ss; CLAUDIA HÄNZI, op. cit., p. 114 sv.).
7. 7.1 En ce qui concerne la personne assistée, on peut dégager de la pratique les principes suivants pour ce qui est de la prise en considération des contributions d'entretien, des dettes fiscales et des autres dettes :
7.1.1 Pour ce qui est des contributions d'entretien, les normes CSIAS prévoient que si une personne aidée est assujettie à une dette alimentaire, celle-ci ne peut pas être prise en compte dans le budget d'aide sociale, car elle n'est pas destinée à son entretien propre, ni à celui de son ménage. Les ayants droit à une pension alimentaire se trouvant en difficultés financières du fait que ces pensions ne leur sont pas versées, peuvent faire valoir un droit à une avance et à une aide au recouvrement. Si elles ont en plus besoin d'aide sociale, elles feront valoir leur propre droit dans leur commune (normes CSIAS 04/05 F.3-1). Si le débiteur alimentaire tombe dans une situation de détresse en raison des ressources effectivement à sa disposition, il peut demander l'aide sociale. En plus, il peut faire une demande de réduction de ses dettes alimentaires. En vertu du principe de la subsidiarité de l'aide sociale, il peut y être obligé (HEINRICH DUBACHER/BERNADETTE VON DESCHWANDEN, Un avis aux débiteurs doit-il être accepté ? in: ZeSo 2008 2 p. 24; cf. également FamPra.ch 2005 p. 138).
7.1.2 Par ailleurs, selon la doctrine, l'aide sociale ne doit servir à couvrir ni les impôts courants ni les impôts arriérés. Le paiement des impôts ne fait pas partie du minimum social de la personne assistée. En vertu du principe de la subsidiarité, celle-ci doit chercher à obtenir une remise ou un sursis (FELIX WOLFFERS, op. cit., p. 151; CLAUDIA HÄNZI, op. cit., p. 135). Les normes CSIAS (04/05 C.1-8) s'expriment dans le même sens. Les impôts qui sont dus à partir d'un certain revenu, pourront généralement être acquittés au moyen de la franchise.
7.1.3 Enfin, l'aide sociale a pour but de couvrir les besoins actuels. Elle ne peut en principe servir à amortir des dettes. Des exceptions peuvent être admises lorsque le non-paiement des dettes pourrait entraîner une nouvelle situation d'urgence à laquelle seule l'aide sociale pourrait remédier. Ainsi l'aide sociale peut-elle être amenée à prendre en charge les arriérés de loyer. L'autorité décide de la prise en charge de dettes de cas en cas sur la base d'une pesée des intérêts (FELIX WOLFFERS, op. cit., p. 152; CLAUDIA HÄNZI, op. cit., p. 137).
7.2 En ce qui concerne le concubin non bénéficiaire, les normes CSIAS 12/07 H.10 ("Aide à la pratique") prévoient une réglementation particulière. Pour le partenaire non bénéficiaire, on établit un budget "élargi". Les revenus dépassant les besoins sont pris en compte dans leur intégralité à titre de revenu dans le budget du partenaire demandant l'aide sociale ("contribution de concubinage"). Le budget élargi comprend divers postes, dont les obligations d'entretien et les impôts courants (1/12 des impôts annuels). Le remboursement de dettes fiscales est pris en compte dans le budget pour autant qu'un accord correspondant ait été conclu avec l'autorité fiscale et que les paiements soient réellement effectués. Le remboursement d'autres dettes n'est pris en considération que si la personne peut prouver qu'au cours des six mois écoulés, elle a régulièrement payé les acomptes (voir aussi HEINRICH DUBACHER/BERNADETTE VON DESCHWANDEN, Comment calculer la contribution de concubinage ?, in: ZeSo 2007 3 p. 19).
7.2.1 La pratique susmentionnée à propos des obligations d'entretien du concubin (non bénéficiaire de l'aide sociale) s'inscrit dans la ligne de la jurisprudence selon laquelle les obligations d'entretien découlant du droit de la famille ont un caractère prioritaire. Le conjoint débiteur d'entretien ne saurait en principe invoquer un devoir d'assistance à l'égard de son concubin pour se soustraire en tout ou partie à son obligation d'entretien (arrêt 5P.15/1995 du 1er mars 1995 consid. 3c; cf. aussi FamPra.ch 2006 p. 149; arrêt 5C.112/2005 du 4 août 2005 consid. 3.2.3). Cela vaut en tout cas aussi longtemps que le montant des contributions d'entretien fixées par un jugement n'a pas été modifié par un tribunal. En cas de diminution des ressources du débiteur après divorce, celui-ci peut demander une modification ou une suppression de la contribution conformément à l'art. 129 al. 1 CC. Selon cette disposition, si la situation du débiteur ou du créancier change notablement et durablement, la rente peut être diminuée, supprimée ou suspendue pour une durée déterminée; une amélioration de la situation du créancier n'est prise en compte que si une rente permettant d'assurer son entretien convenable a pu être fixée dans le jugement de divorce. Ces conditions peuvent par exemple être remplies lors de la naissance d'un enfant dont la filiation est reconnue par le concubin qui devient de ce fait débiteur d'une contribution d'entretien (cf. FamPra.ch 2005 p. 138; arrêt 5C.170/2004 du 27 octobre 2004). En outre, selon l'art. 286 al. 2 CC, si la situation change notablement, le juge modifie ou supprime la contribution d'entretien à la demande du père, de la mère ou de l'enfant.
7.2.2 Si le concubin (non bénéficiaire de l'aide) verse une pension alimentaire manifestement trop élevée par rapport à ses moyens et qu'il renonce à en demander la suppression ou la réduction, alors qu'il aurait de bonnes chances de l'obtenir, cela peut avoir des incidences sur le calcul des besoins du bénéficiaire de l'aide sociale. En cas d'inaction du débiteur après un certain délai, il peut se justifier de faire abstraction - en tout ou partie - de son obligation d'entretien dans le calcul du montant de l'aide allouée (voir, en matière de prestations complémentaires, RCC 1991 p. 143). A défaut, cela reviendrait à faire supporter directement par l'aide sociale des obligations d'entretien sans rapport avec la véritable situation du débiteur.
8. 8.1 En l'espèce, l'arrêté cantonal d'exécution renvoie expressément à son art. 24 aux recommandations de la CSIAS. Les premiers juges admettent que ces normes sont applicables, à titre de droit cantonal supplétif. Ils ont pourtant appliqué aux recourants, considérés comme une unité d'assistance, les principes valables pour les personnes assistées. De manière implicite, ils ont refusé de tenir compte des obligations d'entretien et des autres dettes de G._. Ils n'expliquent toutefois pas pour quels motifs il se justifierait, dans le cas concret, de s'écarter des règles de calcul différentes prévues par les normes CSIAS pour le concubin non bénéficiaire de l'aide sociale (supra consid. 7.2). Certes, la référence dans le droit cantonal aux normes en question n'oblige pas nécessairement les autorités à les appliquer dans leurs moindres détails. Si l'autorité entend s'en écarter elle doit toutefois indiquer les motifs pour lesquels elle statue dans un autre sens. Ces motifs ne ressortent pas du jugement attaqué. Ainsi, en ce qui concerne plus particulièrement l'obligation d'entretien, les premiers juges renvoient G._ à faire reconnaître sa "véritable situation auprès des tiers auxquels il doit des aliments", sans que l'on sache plus précisément si, et le cas échéant dans quelle proportion, les contributions dues seraient manifestement disproportionnées aux ressources du débirentier.
8.2 Il apparaît ainsi que la juridiction cantonale n'a pas examiné le cas sous l'angle des normes pertinentes de la CSIAS, pourtant reconnues par elle applicables à la situation des recourants. Il y a dès lors lieu de constater que le jugement entrepris ne permet pas un examen du litige par le Tribunal fédéral. Celui-ci, en particulier, n'a pas à statuer, pour la première fois en instance fédérale, sur des griefs déjà soulevés par les recourants en instance cantonale, ni à établir elle-même quelles dispositions de droit cantonal ou quel principe seraient éventuellement applicables pour justifier la décision contestée, nonobstant la référence aux normes en question dans le droit cantonal.
9. Il s'ensuit que le recours doit être partiellement admis. La décision attaquée est annulée et la cause est renvoyée à l'instance précédente pour qu'elle se prononce à nouveau à la lumière des considérants qui précèdent.
10. Les frais judiciaires sont mis à la charge de la Ville de Neuchâtel qui succombe et dont l'intérêt patrimonial est en cause (art. 66 al. 4 LTF). La Ville versera une indemnité de dépens aux recourants, qui obtiennent gain de cause avec l'assistance d'une avocate (art. 68 al. 1 LTF). La demande d'assistance judiciaire est ainsi sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis en ce sens que le jugement du Tribunal administratif du canton de Neuchâtel du 31 mars 2009 est annulé, la cause étant renvoyée à ce tribunal pour nouvelle décision au sens des motifs.
2. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge de la Ville de Neuchâtel.
3. La Ville de Neuchâtel versera aux recourants la somme de 2800 fr. à titre de dépens pour la dernière instance.
4. Le présent arrêt est communiqué aux parties et au Tribunal administratif du canton de Neuchâtel.
Lucerne, le 12 février 2010
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Ursprung Hofer