Faits :
A.
La Procureure Nathalie Guillaume-Gentil Gross a instruit l'affaire dite B._ et soutenu l'accusation devant le Tribunal criminel du Littoral et du Val-de-Travers qui a rendu son jugement de condamnation le 5 octobre 2018, lequel a fait l'objet d'appels actuellement pendants devant la Cour pénale du Tribunal cantonal de la République et canton de Neuchâtel. La déclaration d'appel de la Procureure précitée a en l'occurrence été rédigée le 4 décembre 2018. Cette dernière a occupé la fonction de procureure ordinaire jusqu'à fin décembre 2018, avant d'exercer dès le 1er janvier 2019 celle de juge auprès du Tribunal du Littoral et du Val-de-Travers. Le 4 janvier 2019, le Conseil de la magistrature a désigné Nathalie Guillaume-Gentil Gross en qualité de procureure suppléante extraordinaire pour la procédure d'appel précitée.
Le 20 décembre 2018, A._ a déposé une demande de récusation de la Procureure Nathalie Guillaume-Gentil Gross au motif qu'elle avait été nommée dès le 1er janvier 2019 en tant que juge auprès du Tribunal criminel ayant rédigé le jugement du 5 octobre 2018.
Par arrêt du 24 janvier 2019, l'autorité de recours en matière pénale du Tribunal cantonal a laissé indécise la question de la tardiveté de la demande de récusation déposée par le recourant, considérant qu'elle pouvait de toute manière être rejetée; elle a jugé que cette demande était non seulement manifestement infondée, mais également téméraire.
B.
Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'arrêt du 24 janvier 2019 et d'admettre la demande de récusation de la Procureure Nathalie Guillaume-Gentil Gross. Le recourant demande par ailleurs l'octroi de l'assistance judiciaire.
Invitée à se déterminer, l'autorité précédente dépose des observations et persiste pour le surplus dans les termes des considérants de l'arrêt entrepris. Quant au Ministère public, il renonce à déposer des déterminations, tout en concluant au rejet du recours. Le recourant réplique.

Considérant en droit :
1.
Conformément aux art. 78 et 92 al. 1 LTF, une décision relative à la récusation d'un magistrat pénal peut faire immédiatement l'objet d'un recours en matière pénale. Le recourant, auteur de la demande de récusation, a qualité pour recourir (<ref-law>). Pour le surplus, le recours a été interjeté en temps utile (<ref-law>) contre une décision rendue en dernière instance cantonale (<ref-law>) et les conclusions prises sont recevables (<ref-law>). Il y a donc lieu d'entrer en matière.
2.
Saisi d'un recours en matière pénale, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), alors qu'il n'examine la violation de droits fondamentaux ou de dispositions de droit cantonal que si ce grief a été invoqué et motivé par le recourant, conformément au principe d'allégation (<ref-law>). Dans ce cas, l'acte de recours doit contenir, sous peine d'irrecevabilité, un exposé succinct de la disposition constitutionnelle ou légale violée et préciser de façon 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).
3.
Dans son écriture, le recourant présente son propre exposé des faits. Or, le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Le recourant ne peut critiquer la constatation de faits qui importent pour le jugement de la cause que si ceux-ci ont été établis en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire (cf. <ref-law>), ce qu'il lui appartient de démontrer par une argumentation répondant aux exigences de l'<ref-law>, respectivement de l'<ref-law> (cf. <ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 4.1.2 p. 62). En l'espèce, le recours ne comporte aucune démonstration du caractère arbitraire de l'état de fait de la décision attaquée, de sorte qu'il n'y a pas lieu de prendre en considération d'autres faits que ceux retenus dans ladite décision. Les critiques qui se fondent sur des faits non établis sont irrecevables.
4.
Le recourant soutient que sa demande de récusation du 20 décembre 2018 n'était ni mal-fondée, ni téméraire. Il soutient que la Procureure Nathalie Guillaume-Gentil Gross ne pourrait représenter le Ministère public devant la Cour pénale du Tribunal cantonal puisqu'elle officie simultanément comme juge de première instance auprès du Tribunal régional du Littoral et du Val-de-Travers. Il invoque notamment le principe de l'égalité des armes garanti par l'art. 6 CEDH.
4.1.
4.1.1. Un magistrat est récusable, aux termes de l'art. 56 let. f CPP, lorsque d'autres motifs, notamment un rapport d'amitié étroit ou d'inimitié avec une partie ou son conseil juridique, sont de nature à le rendre suspect de prévention. Cette disposition a la portée d'une clause générale recouvrant tous les motifs de récusation non expressément prévus aux lettres précédentes. Elle correspond à la garantie d'un tribunal indépendant et impartial instituée par les art. 30 al. 1 Cst. et 6 par. 1 CEDH. Elle n'impose pas la récusation seulement lorsqu'une prévention effective du magistrat est établie, car une disposition interne de sa part ne peut guère être prouvée. Il suffit que les circonstances donnent l'apparence de la prévention et fassent redouter une activité partiale du magistrat. Seules les circonstances constatées objectivement doivent être prises en considération. Les impressions purement individuelles d'une des parties au procès ne sont pas décisives (<ref-ruling> consid. 3.2 p. 74 et les références citées).
Dans la phase de l'enquête préliminaire et de l'instruction, les principes applicables à la récusation sont ceux qui ont été dégagés à l'égard des juges d'instruction, avant l'introduction du CPP (<ref-ruling> consid. 2.2.1 p. 145). En revanche, après la rédaction de l'acte d'accusation, respectivement dans le cadre de procédures de recours, le ministère public devient une partie aux débats, au même titre que le prévenu ou la partie plaignante (art. 104 al. 1 let. c CPP). Par définition, il n'est plus tenu à l'impartialité et il lui appartient en principe de soutenir l'accusation (art. 16 al. 2 in fine CPP). Dans ce cadre, ni les art. 29 et 30 Cst., ni l'art. 6 par. 1 CEDH ne confèrent au prévenu une protection particulière lui permettant de se plaindre de l'attitude du ministère public et des opinions exprimées par celui-ci durant les débats (<ref-ruling> consid. 3.2.2 p. 180; <ref-ruling> consid. 2.2.2 p. 145 s.), le ministère public demeurant néanmoins soumis aux <ref-law>.
4.1.2. Enfin, tel qu'il est garanti par l'art. 6 CEDH, le principe de l'égalité des armes requiert que chaque partie se voie offrir une possibilité raisonnable de présenter sa cause dans des conditions qui ne la placent pas dans une situation de net désavantage par rapport à son adversaire (cf. <ref-ruling> consid. 4.2.1 p. 124; <ref-ruling> consid. 2.1.2.1 p. 229).
4.2. L'instance précédente a en l'occurrence relevé que la demande de récusation de la Procureure intimée avait été formée par un prévenu après la rédaction de l'acte d'accusation, de sorte qu'elle ne voyait pas en quoi une telle demande pourrait être fondée. L'instance précédente ne voyait pas non plus en quoi la nomination en tant que juge de la Procureure intimée ayant rédigé la déclaration d'appel serait de nature à faire douter de son indépendance ou de son impartialité, ni en quoi celle-ci ne serait pas à même d'exercer sa fonction de procureure (extraordinaire) conformément aux exigences de cette charge. L'instance précédente a considéré qu'au moment de rédiger la déclaration d'appel, l'intimée ne se trouvait pas dans une situation de conflit de loyauté vis-à-vis de ses futurs collègues (dès le 1er janvier 2019), étant en outre précisé que le Tribunal criminel, bien que formellement celui du Tribunal régional du Littoral et du Val-de-Travers à Boudry, était en réalité constitué de deux juges siégeant d'ordinaire au Tribunal régional des Montagnes et du Val-de-Ruz.
4.3. Le recourant critique ce raisonnement. Il affirme que la Procureure Nathalie Guillaume-Gentil Gross ne pourrait représenter le Ministère public devant la Cour pénale du Tribunal cantonal lorsqu'elle officie simultanément comme juge de première instance auprès du Tribunal régional du Littoral et du Val-de-Travers, en raison du principe de l'égalité des armes, de l'apparence de la justice et des risques de renvoi de la cause devant ledit tribunal de première instance. Le recourant y voit un cumul de fonctions qui serait incompatible avec les garanties d'indépendance et d'impartialité découlant des art. 6 CEDH et 30 Cst.
Cette dernière critique peut d'emblée être écartée. Le recourant méconnaît en effet que la Procureure intimée intervient en sa seule qualité de partie à la procédure (cf. art. 104 al. 1 let. c CPP), de sorte que les art. 6 CEDH et 30 Cst. - seules dispositions de rang constitutionnel ou conventionnel qu'il a invoquées dans l'acte de recours - ne sont pas applicables pour la récusation de cette magistrate (cf. supra consid. 4.1.1).
Pour le reste, les arguments développés par le recourant ne sont pas convaincants. En effet, la magistrate intimée n'est intervenue dans la procédure pénale litigieuse qu'au titre de procureur ordinaire, puis procureur extraordinaire. Elle n'a pas participé au procès pénal en tant que juge auprès du Tribunal criminel. L'intimée n'était d'ailleurs pas encore membre de ce tribunal lorsqu'il a rendu son jugement de condamnation le 5 octobre 2018. Par ailleurs, contrairement à ce que soutient le recourant, le fait que la Procureure suppléante extraordinaire intimée exerce depuis le 1er janvier 2019 également la fonction de juge de première instance ne constitue pas en soi un motif de récusation. Il sied à cet égard de relever que, selon la jurisprudence du Tribunal fédéral, la collégialité existant entre les membres d'un tribunal ne suffit pas, à elle seule, à fonder une obligation de récusation (cf. <ref-ruling> consid. 5.3; <ref-ruling> consid. 6.4.4). En l'occurrence, la demande de récusation de la magistrate apparaît d'autant moins fondée que la cause est actuellement pendante devant la Cour pénale du Tribunal cantonal. On ne voit en outre pas en quoi le principe de l'égalité des armes - auquel se réfère le recourant - serait violé. En effet, aucun élément ne permet d'affirmer que la magistrate intimée serait concrètement avantagée dans le cadre de la procédure d'appel devant le Tribunal cantonal; les prétendus avantages dont la magistrate intimée bénéficierait en raison de son appartenance à la juridiction de première instance (discussion informelle avec les juges de première instance au sujet de l'affaire; modalités de consultation du dossier, etc.) relèvent de la pure spéculation. Cette juridiction se trouve par ailleurs dessaisie après son prononcé et les débats auront lieu exclusivement devant l'instance d'appel.
Enfin, la question de savoir si, en cas de renvoi de la cause au Tribunal criminel, l'intimée pourrait continuer d'exercer la charge de Procureure suppléante extraordinaire apparaît prématurée et n'a pas à être résolue à ce stade.
En définitive, les éléments avancés par le recourant - pour autant qu'ils soient recevables (cf. consid. 3) - ne fondent pas un motif de récusation.
5.
Enfin, le recourant se réfère dans son mémoire de recours à l'art. 9 de la loi cantonale sur la magistrature de l'ordre judiciaire et la surveillance des autorités judiciaires (LMSA). Ce n'est toutefois qu'au stade de la réplique, qu'il se plaint d'une application arbitraire (art. 9 Cst.) de cette disposition et qu'il motive ce grief conformément aux exigences accrues de motivation posées par l'<ref-law> (cf. supra consid. 2). Or, selon la jurisprudence du Tribunal fédéral, le mémoire de réplique ne saurait être utilisé aux fins de présenter de nouvelles conclusions ou de nouveaux griefs qui auraient déjà pu figurer dans l'acte de recours (cf. <ref-ruling> consid. 1.2.3); il s'ensuit que ce grief est irrecevable. Au demeurant, ce moyen tiré de la violation du droit cantonal est également irrecevable au motif qu'il est soulevé pour la première fois devant le Tribunal fédéral, les griefs juridiques nouveaux n'étant en effet recevables devant la cour de céans que lorsqu'ils relèvent du droit fédéral (cf. <ref-ruling> consid. 4.4.3 p. 156 s.).
6.
Il s'ensuit que le recours est rejeté dans la mesure où il est recevable.
Dès lors que le recourant est dans le besoin et que ses conclusions ne paraissaient pas d'emblée vouées à l'échec, sa requête d'assistance judiciaire doit être admise (<ref-law>). Par conséquent, il y a lieu de le dispenser des frais judiciaires et d'allouer une indemnité à son mandataire, désigné comme avocat d'office (<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 est admise. Me Olivier Bigler est désigné comme avocat d'office du recourant et une indemnité de 2'000 fr. lui est allouée à titre d'honoraires, à payer par la caisse du Tribunal fédéral. Il n'est pas perçu de frais judiciaires.
3.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal de la République et canton de Neuchâtel, Autorité de recours en matière pénale.
Lausanne, le 13 juin 2019
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
La Greffière : Arn