Faits :
A.
Les époux A.X._ et B.X._ sont contribuables neuchâtelois.
B.
B.a. Le 8 décembre 2008, le Service des contributions de la Ville de Neuchâtel a rendu des décisions déterminant la part que B.X._ devait supporter des impôts cantonaux et communaux du couple (ci-après: la "part-épouse") pour les années 1998, 2001, 2002, 2004, 2005, 2006 et 2007, la responsabilité solidaire de l'épouse ayant pris fin en raison de l'insolvabilité de son mari. Les contribuables ont élevé réclamations contre ces décisions, que l'autorité fiscale a jugées irrecevables (décision sur réclamation du 22 janvier 2010). Par arrêt du 28 novembre 2011, la Cour de droit public du Tribunal cantonal de Neuchâtel (ci-après: le Tribunal cantonal) a admis le recours formé par les contribuables contre cette décision et renvoyé le dossier au Service cantonal des contributions, qui était désormais compétent (ci-après: le Service cantonal), pour nouvelle décision sur réclamation. Celle-ci est intervenue le 4 mars 2014.
Une procédure parallèle - et additionnelle s'agissant de 2007 - avait été menée pour fixer le montant des parts-épouse des périodes fiscales 2007 et 2008. Le calcul effectué par le Service cantonal avait été annulé par arrêts du 5 mai 2011 du Tribunal cantonal. A la suite de ces arrêts, le Service cantonal a rendu, le 26 juillet 2011, une décision sur réclamation portant sur la part-épouse en matière d'impôt cantonal et communal 2007, qui n'a pas été contestée et qui est partant entrée en force.
B.b. Le 11 avril 2014, A.X._ et B.X._ ont contesté la décision sur réclamation du 4 mars 2014 auprès du Tribunal cantonal. Entre autres griefs, ils invoquaient la prescription, faisant valoir qu'ils avaient réglé des montants d'impôts qui avaient été attribués contre leur volonté à des périodes prescrites et se prévalaient de l'accord qu'ils avaient conclu le 20 février 2008 avec le chef du Département de la justice, de la sécurité et des finances du canton de Neuchâtel (ci-après: l'accord de 2008), qui avait pour but de régler l'entier du contentieux, fiscal et non fiscal, qui les opposait au canton. Ils soutenaient que cet accord avait été résilié à tort par l'autorité, au motif, selon eux erroné, qu'ils n'en avaient pas respecté les termes.
Le Tribunal cantonal a statué par arrêt du 6 octobre 2016. Il a d'abord constaté que le litige ne concernait désormais que les périodes fiscales 2004 à 2006 (en raison de la prescription pour les années antérieures et du fait que la part-épouse de la période fiscale 2007 était définitivement réglée par la décision sur réclamation du 26 juillet 2011). Au fond, les juges cantonaux ont souligné que le litige avait pour seul objet le calcul de part-épouse, soit la part due par l'épouse sur le montant d'impôt global du couple. Dans ces circonstances, il n'y avait pas lieu d'examiner, comme les contribuables le requéraient, les décomptes d'encaissements des montants d'impôts payés, puisque ce point était étranger au litige. Pour la même raison, les contribuables ne pouvaient pas se prévaloir de l'accord de 2008, qui n'avait pas de lien avec l'objet du litige. Cet accord avait du reste été résilié par le Chef du département de la justice, de la sécurité et des finances du canton de Neuchâtel le 16 septembre 2008. En définitive,le Tribunal cantonal a admis très partiellement le recours pour les années 2004 à 2006 et fixé les parts-épouse à 19'354 fr. 50 pour 2004, 19'096 fr. 50 pour 2005 et 23'225 fr. 70 pour 2006, en retenant les montants, plus favorables aux contribuables, ressortant des décisions de taxation, sommes auxquelles devaient être ajoutés la part d'intérêts rémunératoires et les frais de recouvrement afférents à la part d'impôt de l'épouse, sous déduction du pro rata des acomptes payés par le couple.
C.
A.X._ et B.X._ forment un recours en matière de droit public au Tribunal fédéral à l'encontre de l'arrêt du 6 octobre 2016 du Tribunal cantonal en demandant, sous suite de frais et dépens, son annulation et le renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Ils se plaignent en substance d'une violation des règles sur le fardeau de la preuve en lien avec l'accord de 2008, dont ils soutiennent qu'il est toujours applicable, font valoir qu'ils ont réglé des montants d'impôts qui avaient été attribués aux périodes fiscales les plus anciennes contrairement à leur volonté, et invoquent une violation du principe de la célérité.
Par ordonnance du 14 décembre 2016, la Cour de céans a constaté que la requête d'effet suspensif contenue dans le recours était désormais sans objet, les autorités cantonales ayant déclaré avoir suspendu la procédure de recouvrement des impôts jusqu'à droit connu sur le recours.
Le Tribunal cantonal et le Service cantonal se réfèrent aux motifs de l'arrêt attaqué et concluent au rejet du recours. L'Administration fédérale s'est déterminée et a conclu au rejet du recours dans la mesure de sa recevabilité.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office et avec pleine cognition la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 417; <ref-ruling> consid. 1 p. 644).
1.1. Le recours est dirigé non seulement contre l'arrêt attaqué, mais également contre un arrêt du Tribunal cantonal du 5 octobre 2016 concernant l'impôt cantonal et communal (ICC) et l'impôt fédéral direct (IFD) 2011 et 20112 (CDP.2015.20-FISC, procédure 2C_1080/2016 et 2C_1081/2016 devant la Cour de céans). Les recourants expliquent n'avoir formé qu'une seule écriture à l'encontre de ces deux arrêts, parce que les arguments qu'ils y développent seraient pertinents pour les deux affaires.
Aux termes de l'art. 24 al. 1 PCF applicable par renvoi de l'art. 71 LTF, le demandeur qui entend exercer plusieurs actions contre le même défendeur peut les joindre dans une seule demande si le Tribunal fédéral est compétent pour connaître de chacune d'elles.
Il n'est pas exclu qu'un seul acte de recours soit dirigé contre deux décisions qui ont été notifiées séparément, lorsque celles-ci présentent un lien de connexité. Dans un tel cas, le Tribunal fédéral joint les causes pour des motifs d'économie de procédure et statue dans un seul arrêt en application de l'art. 24 PCF (cf. par exemple arrêt 5A.716/2017 du 5 octobre 2017 consid. 2). En matière d'impôts directs, il est fréquent que l'instance précédente traite dans un seul arrêt à la fois de l'IFD et de l'ICC, ce qui est admissible (cf. <ref-ruling> consid. 1.3.1 p. 262 s.), de sorte que la jurisprudence admet aussi que le recourant ne forme qu'un seul recours pour contester les deux impôts (<ref-ruling> consid. 1.3.2 p. 263 s.). Dans un tel cas, le Tribunal fédéral joint aussi les causes en application de l'art. 24 PCF (cf. par exemple arrêt 2C_1018/21015 du 2 novembre 2017 consid. 1).
En l'espèce toutefois, les deux arrêts que les recourants contestent dans leur unique recours ne présentent pas de lien de connexité: ils concernent des périodes fiscales différentes et traitent de questions matérielles différentes. Les recourants soutiennent certes que la question de la validité de l'accord de 2008 a un impact sur les deux affaires. Le point de savoir si ce seul élément est suffisant pour admettre le dépôt d'une seule écriture est douteux. Toutefois, étant donné l'issue de la cause, la question de la recevabilité d'un tel recours souffre de rester ouverte.
Dans la suite du raisonnement, seuls les griefs dont on parvient à déterminer qu'ils sont dirigés contre l'arrêt du 6 octobre 2016 seront examinés.
1.2. La décision attaquée est finale (art. 90 LTF) et a été rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF), dans une cause de droit public (art. 82 let. a LTF) qui ne tombe sous le coup d'aucune des exceptions prévues à l'art. 83 LTF. La voie du recours en matière de droit public est donc ouverte (cf. également l'art. 73 al. 1 de la loi fédérale du 14 décembre 1990 sur l'harmonisation des impôts directs des cantons et des communes [LHID; RS 642.14]).
1.3. S'agissant de la qualité pour recourir, l'art. 89 al. 1 LTF prévoit que peut former un recours en matière de droit public quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (let. a), est particulièrement atteint par la décision ou l'acte normatif attaqué (let. b) et a un intérêt digne de protection à son annulation ou à sa modification (let. c). Ces trois conditions sont cumulatives (cf. <ref-ruling> consid. 2.2 in fine p. 43).
Si la recourante remplit indubitablement ces trois conditions, on peut en revanche se demander si le recourant est particulièrement atteint par la décision attaquée (art. 89 al. 1 let. b LTF) et s'il a un intérêt digne de protection à sa modification (art. 89 al. 1 let. c LTF), puisque le litige ne concerne que la détermination de la part des impôts du couple qui doit être payée par la recourante en raison de l'insolvabilité constatée du recourant. Etant donné l'issue du recours, cette question souffre aussi de rester indécise.
1.4. Il faut encore relever que les recourants n'ont pris que des conclusions en annulation et en renvoi, alors que le Tribunal fédéral a un pouvoir général de réforme (art. 107 al. 2 LTF); la réserve de l'art. 73 al. 3 LHID, encore en vigueur au moment du dépôt du recours (abrogée au 1er janvier 2017; RO 2015 779), devait de toute façon céder le pas devant l'art. 107 al. 2 LTF (<ref-ruling> consid. 1.5.3 p. 192). Les conclusions en renvoi sont toutefois admissibles en l'occurrence, dès lors que, comme les recourants soulèvent des griefs formels, le Tribunal fédéral, s'il leur donnait gain de cause, se verrait tenu de renvoyer l'affaire devant l'instance cantonale pour qu'elle statue à nouveau (cf. <ref-ruling> consid. 1.3 p. 317; arrêt 2C_674/2015 du 26 octobre 2017 consid. 2.2).
1.5. Au surplus, le recours a été déposé en temps utile (cf. art. 100 al. 1 LTF) et dans les formes prescrites (cf. art. 42 LTF). Il convient donc d'entrer en matière.
2.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Toutefois, il n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant (cf. art. 106 al. 2 LTF). L'acte de recours doit alors, pour que le grief soit examiné, contenir un exposé succinct des droits et principes constitutionnels violés et préciser de manière claire et détaillée en quoi consiste la violation (cf. <ref-ruling> consid. 1.3 p. 41; <ref-ruling> consid. 2.2 p. 232).
2.2. Pour statuer, le Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (art. 105 al. 1 LTF), à moins que ceux-ci n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (<ref-ruling> consid. 2.3.1 p. 244; <ref-ruling> consid. 2 p. 117) - ou en violation du droit au sens de l'art. 95 LTF (art 105 al. 2 LTF), et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (cf. art. 97 al. 1 LTF). Il incombe au recourant de démontrer d'une manière circonstanciée, conformément aux exigences de motivation de l'art. 106 al. 2 LTF, que les faits ont été établis de manière inexacte (cf. <ref-ruling> consid. 1.3 p. 41; <ref-ruling> consid. 2.2 p. 232). 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 divergeant de celui qui est contenu dans l'acte attaqué (<ref-ruling> consid. 3.1.2 p. 34; <ref-ruling> consid. 5.1 p. 356). Le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 2.3 p. 266).
Dans la mesure où les recourants présentent de manière appellatoire leur propre version des faits ou complètent librement l'état de fait, sans invoquer ou établir ni l'arbitraire, ni une autre violation des droits fondamentaux, le Tribunal fédéral ne peut pas en tenir compte. Il statuera donc sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
3.
3.1. La prescription ou la péremption sont des questions de droit matériel que le Tribunal fédéral examine d'office lorsqu'elles jouent en faveur du contribuable (cf. <ref-ruling> consid. 3.2 p. 171). Il en va de même en matière d'impôt cantonal et communal, dans la mesure où la matière est harmonisée (cf. arrêt 2C_999/2014 du 15 janvier 2015 consid. 4.1, résumé in Archives 83 p. 516). En l'occurrence, l'art. 187 al. 3 de la loi neuchâteloise sur les contributions directes (RS/NE 631.0) prévoit, à l'instar de l'art. 47 al. 2 LHID, une règle de prescription absolue des créances d'impôt, qui est acquise dans tous les cas dix ans après la fin de l'année au cours de laquelle la taxation est entrée en force.
3.2. En l'occurrence, selon les faits constatés dans l'arrêt attaqué, la décision de taxation définitive pour l'impôt cantonal et communal de la période 2004 est intervenue le 21 septembre 2006. La prescription absolue de la créance d'impôt cantonal et communal afférente à cette période ayant été acquise le 31 décembre 2016, la question de la détermination de la part-épouse afférente à cette période n'a plus d'objet. Sur ce point, le recours sera donc admis, étant rappelé que, s'agissant des périodes fiscales antérieures, l'arrêt attaqué a constaté que les créances d'impôt étaient prescrites (cf. supra consid. B.b).
4.
Les recourants reprochent d'abord au Tribunal cantonal de ne pas avoir donné suite à leur demande d'instruction tendant à examiner la validité de l'accord de 2008 et de s'être limité à tenir pour établi que cet accord avait été résilié. Or, cette question aurait dû faire l'objet, comme ils l'avaient requis, d'une instruction menée conformément aux règles de répartition du fardeau de la preuve découlant de l'art. 8 du Code civil.
4.1. Avant d'examiner si les règles relatives au fardeau de la preuve ont été violées en lien avec l'accord de 2008, il est nécessaire de se demander si on peut reprocher aux juges cantonaux de ne pas avoir donné suite à la demande d'instruction des recourants. Si l'on ne peut leur faire ce grief, la question du respect des règles sur le fardeau de la preuve n'aura alors logiquement plus d'objet.
4.2. Il ressort de l'arrêt attaqué que les juges précédents ont estimé que l'accord de 2008 n'avait pas de lien avec l'objet du litige, qui ne concernait que la quote-part de l'épouse. Ils ont ajouté que cet accord avait du reste été résilié par le Chef du département concerné.
Le point de savoir si une instruction devait être menée pour juger de la validité de l'accord de 2008 relève du droit d'être entendu (art. 29 al. 2 Cst.). Cette disposition garantit notamment le droit pour l'intéressé d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, lorsque cela est de nature à influer sur la décision à rendre. L'autorité peut cependant renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de forger sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 6.3.1 p. 298 s. et les arrêts cités).
4.3. Cette question relève ainsi des droits constitutionnels, que le Tribunal fédéral n'examine que si un grief a été formulé à cet égard (art. 106 al. 2 LTF; cf. supra consid. 3.1). Or, les recourants ne font valoir aucune violation du droit d'être entendu en lien avec le refus des juges cantonaux d'instruire sur la question de la validité de l'accord de 2008, ni se prévalent d'une appréciation arbitraire des preuves sur ce point. Au surplus, ils ne démontrent pas non plus en quoi l'appréciation des juges cantonaux, selon laquelle les recourants ne pouvaient de toute manière rien tirer de l'accord de 2008, qui était étranger au litige qui avait pour seul objet la fixation du montant de la part-épouse, serait arbitraire. La simple affirmation que la question de la validité de la résiliation de l'accord de 2008 "aurait à n'en pas douter des conséquences sur les montants réclamés" ne suffit pas au regard des exigences de l'art. 106 al 2 LTF.
4.4. Dans ces circonstances, la violation des règles sur le fardeau de la preuve soulevée par les recourants n'a pas à être examinée.
5.
Sous le titre "De l'affectation unilatérale des montants versés à titre d'impôts" et "De la prescription", les recourants, dans la mesure où leur argumentation est compréhensible, reprochent en substance au Tribunal cantonal de ne pas avoir jugé nécessaire d'examiner les décomptes d'encaissement d'impôts qu'ils avaient effectués, alors qu'ils avaient expressément indiqué vouloir affecter ces versements au paiement des dettes d'impôt les plus récentes et que cette volonté avait été bafouée par l'autorité fiscale. Ils soutiennent que la question de l'affectation des montants d'impôts payés devait être tranchée, car elle avait un impact sur la prescription des créances fiscales.
5.1. Il ressort de l'arrêt attaqué que les juges cantonaux ont effectivement retenu qu'il n'était pas nécessaire d'examiner les décomptes d'encaissement des impôts versés par les recourants, parce que le litige à trancher ne concernait que la question de la détermination de la part-épouse. Ce faisant, les juges cantonaux ont considéré que le point de savoir à quels impôts leurs paiements avaient été affectés n'avait aucun lien avec l'objet du litige.
5.2. Ici encore, les recourants n'allèguent ni a fortiori ne démontrent que l'appréciation anticipée des preuves à laquelle se sont livrés les juges cantonaux serait contraire à l'art. 29 al. 2 Cst. (cf. supra consid. 4.2 et 4.3). Formulé de manière insuffisante au regard des exigences de l'art. 106 al. 2 LTF, ce grief ne sera pas non plus examiné.
En outre, les recourants perdent de vue que l'objet du litige devant les juges cantonaux portait uniquement sur la détermination de la part due par l'épouse sur le montant total des impôts du couple. Le fait que les recourants y mêlent des questions relatives à l'affectation de leurs versements d'impôts, qui ne sont pas liées à cette problématique spécifique, n'y change rien. Cela étant, si des impôts d'années litigieuses ont déjà été payés, alors la question de la détermination de la part épouse serait sans objet.
6.
Invoquant finalement l'art. 29 al. 1 Cst., l'art. 6 par. 1 CEDH et l'art. 14 ch. 3 let. c Pacte ONU II, les recourants se plaignent de ce que les juges cantonaux ont gravement violé le principe de célérité en mettant presque trois ans pour statuer sur leur recours.
6.1. Les art. 6 par. 1 CEDH et 14 Pacte ONU II ne sont pas applicables dans les procédures fiscales qui n'ont pas un caractère pénal (ATF 140 68 consid. 9.2 p. 74; arrêt 2C_741/2017 du 26 janvier 2017 consid. 9.1).
6.2. En vertu de l'art. 29 al. 1 Cst., toute personne a droit, dans une procédure judiciaire ou administrative, à ce que sa cause soit traitée équitablement et jugée dans un délai raisonnable. Selon la jurisprudence, il appartient au justiciable, en application du principe de la bonne foi (art. 5 al. 3 Cst.), d'entreprendre ce qui est en son pouvoir pour que l'autorité fasse diligence, que ce soit en l'invitant à accélérer la procédure ou en recourant, le cas échéant, pour retard injustifié, car il serait contraire à ce principe qu'un justiciable puisse valablement soulever ce grief devant l'autorité de recours, alors qu'il n'a entrepris aucune démarche auprès de l'autorité précédente, afin de remédier à cette situation. En outre, dès que l'autorité a statué, le justiciable perd en principe tout intérêt juridique à faire constater un éventuel retard à statuer (cf. <ref-ruling> consid. 2.1 p. 500; <ref-ruling> consid. 5.2 p. 332; arrêt 2C_1014/2013 du 22 août 2014 consid. 7.1 et 7.2 non publiés in <ref-ruling> mais in Pra 2015/54 p. 424).
6.3. En l'occurrence, l'on peut certes s'étonner du temps mis par l'autorité précédente à statuer dans un litige qui n'apparaît pas particulièrement complexe. Cela étant, il ne semble pas - et les recourants ne le soutiennent du reste pas - qu'ils aient agi auprès de l'autorité précédente pour lui demander de faire diligence, pas plus qu'ils ne se sont plaints d'un retard injustifié auprès de la Cour de céans (cf. art. 94 LTF). Ils n'expliquent pas non plus en quoi il y aurait encore un intérêt à faire constater un éventuel retard à statuer maintenant que la décision a été rendue. La critique est donc infondée.
7.
Les considérants qui précèdent conduisent à l'admission partielle du recours, en ce sens que la part de l'impôt cantonal et communal due par l'épouse pour la période fiscale 2004 est prescrite. L'arrêt attaqué est confirmé pour le surplus.
N'ayant obtenu que partiellement gain de cause, les recourants devraient en principe supporter une part des frais judiciaires, solidairement entre eux (art. 66 al. 1 et 5 LTF). Cela étant, dans la mesure où on ignore si et dans quelle mesure la cause a encore un objet (cf. supra consid. 5.2 in fine), et compte tenu également du faible montant en jeu, aucun frais judiciaire ne sera mis à leur charge. L'autorité intimée, soit pour elle le canton de Neuchâtel, dont l'intérêt patrimonial est en jeu (art. 66 al. 4 LTF), supportera les frais dans la mesure où elle succombe. Il n'est pas alloué de dépens, dès lors que les recourants ont obtenu partiellement gain de cause sans l'aide d'un mandataire professionnel (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis.
2.
L'arrêt du 6 octobre 2016 du Tribunal cantonal est réformé, en ce sens que la part-épouse pour l'impôt cantonal et communal de la période fiscale 2004 est supprimée. L'arrêt attaqué est confirmé pour le surplus.
3.
Les frais judiciaire, arrêtés à 500 fr., sont mis à la charge du canton de Neuchâtel.
4.
Il n'est pas alloué de dépens.
5.
Le présent arrêt est communiqué aux recourants, au Service des contributions de la République et canton de Neuchâtel, au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, et à l'Administration fédérale des contributions.
Lausanne, le 18 décembre 2017
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Vuadens