Faits :
A.
A._, ressortissant indien né en 1995, est arrivé en Suisse à une date indéterminée. Le 9 septembre 2017, il a été interpellé par la police neuchâteloise, qui a constaté qu'il se trouvait sans titre de séjour valable en Suisse ou en Europe.
B.
Par décision du 11 septembre 2017, le Service des migrations du canton de Neuchâtel (ci-après: le Service cantonal) a prononcé le renvoi de Suisse de A._, avec un délai de départ au 25 septembre 2017. La décision indiquait que le renvoi était immédiatement exécutoire et qu'un recours n'aurait pas d'effet suspensif.
Le 18 septembre 2017, A._ a recouru contre ce prononcé auprès du Département de l'économie et de l'action sociale de la République et canton de Neuchâtel (ci-après: le Département). Dans ce cadre, il a sollicité l'octroi de mesures provisionnelles tendant à l'autoriser à séjourner en Suisse pendant la procédure de recours, en faisant valoir qu'il avait entrepris des démarches en vue de se marier avec une ressortissante portugaise rencontrée en 2016 et que son intérêt à demeurer en Suisse le temps nécessaire à la conclusion de son mariage l'emportait sur l'intérêt public à l'exécution immédiate de son renvoi.
Par décision incidente du 29 septembre 2017, le Département a rejeté la demande de restitution de l'effet suspensif.
Contre cette décision, A._ a formé un recours à la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel (ci-après: le Tribunal cantonal). Il a notamment produit un courrier du Service de l'état civil de la Ville de Genève du 2 octobre 2017 confirmant qu'une procédure préparatoire au mariage était en cours. Le 19 octobre 2017, il a déposé une attestation de l'Office cantonal de la population et des migrations du canton de Genève indiquant qu'il avait formulé une demande d'autorisation de séjour dans ce canton, actuellement à l'examen.
Le Tribunal cantonal a rejeté le recours par arrêt du 20 octobre 2017.
C.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 20 octobre 2017 et de l'autoriser à séjourner en Suisse pendant la procédure préparatoire au mariage. Il sollicite l'effet suspensif et l'octroi de l'assistance judiciaire.
Le Service cantonal se réfère au contenu de l'arrêt entrepris et conclut au rejet du recours. Le Département conclut au rejet du recours dans la mesure de sa recevabilité. Le Tribunal cantonal ne formule pas d'observations, se réfère aux motifs de son arrêt et conclut au rejet du recours. Le Secrétariat d'Etat aux migrations ne s'est pas déterminé.
Par ordonnance du 11 décembre 2017, le Président de la II e Cour de droit public du Tribunal fédéral a refusé d'accorder l'effet suspensif au recours. Le 12 décembre 2017, le Tribunal fédéral a renoncé provisoirement à exiger une avance de frais et indiqué à A._ qu'il serait statué ultérieurement sur l'octroi de l'assistance judiciaire.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2.1 p. 397; <ref-ruling> consid. 2 p. 59).
1.1. La décision entreprise porte uniquement sur le refus de restituer l'effet suspensif au recours formé par le recourant contre la décision du Service cantonal du 11 septembre 2017 ordonnant son renvoi de Suisse. Elle ne concerne pas la question de l'éventuel droit du recourant à une autorisation de séjour en vue de son mariage, qui fait l'objet, selon les faits de l'arrêt entrepris, d'une procédure dans le canton de Genève (cf., sur cette problématique, <ref-ruling> consid. 3.7 p. 359 s.; arrêt 2C_950/2014 du 9 juillet 2015 consid. 4.2 et les arrêts cités).
1.2. La décision de refus de restituer l'effet suspensif ne met pas un terme à la procédure et n'est donc pas une décision finale (cf. <ref-law>). Elle constitue une décision incidente au sens de l'<ref-law> (cf. <ref-ruling> consid. 2.1 p. 606; <ref-ruling> consid. 1 p. 476; arrêt 2C_819/2016 du 14 novembre 2016 consid. 1.1). La voie de recours contre une décision incidente est déterminée par le litige principal (cf. <ref-ruling> consid. 1.2 p. 269). En l'occurrence, celui-ci porte sur le renvoi de Suisse du recourant, prononcé par le Service cantonal sur la base de l'art. 64 al. 1 let. a LEtr (RS 142.20). Or, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent cette question (art. 83 let. c ch. 4 LTF). Il s'ensuit que le présent recours ne peut être reçu en qualité de recours en matière de droit public (cf. arrêts 2D_9/2017 du 3 octobre 2017 consid. 1.3; 2C_819/2016 du 14 novembre 2016 consid. 1.1).
1.3. Seule entre en considération en l'espèce la voie du recours constitutionnel subsidiaire (cf. <ref-law>). Le recourant n'a pas formé, même à titre subsidiaire, un tel recours. L'intitulé erroné du recours ne nuit cependant pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (cf. <ref-ruling> consid. 1.1 p. 370).
1.4. Dans la mesure où elle a été rendue par une autorité cantonale de dernière instance (cf. <ref-law>), une décision de renvoi, ainsi qu'une décision incidente en lien avec le renvoi si les conditions de l'<ref-law> sont réunies (cf. <ref-law>), peut être attaquée par la voie du recours constitutionnel subsidiaire (cf. <ref-ruling> consid. 1.1 p. 307).
Conformément à l'<ref-law>, une décision incidente notifiée séparément qui ne porte pas sur la compétence ou sur une demande de récusation peut faire l'objet d'un recours si elle peut causer un préjudice irréparable, lequel doit être de nature juridique (cf. <ref-ruling> consid. 2.2 p. 801). Le refus d'accorder l'effet suspensif à une décision de renvoi est susceptible de causer un préjudice irréparable au sens de l'<ref-law> lorsque la personne allègue de manière défendable un droit à une autorisation de séjour en vue du mariage fondé sur l'art. 14 Cst. et l'art. 12 CEDH (cf. arrêt 2D_9/2017 du 3 octobre 2017 consid. 1.5). Tel est le cas en l'espèce. Le recourant invoque en effet un droit à demeurer en Suisse en vue de se marier et il ressort de l'arrêt entrepris qu'une procédure préparatoire au mariage a été ouverte dans le canton de Genève.
La décision entreprise, qui a été rendue par une autorité cantonale de dernière instance, peut donc sur le principe faire l'objet d'un recours constitutionnel subsidiaire.
1.5. A qualité pour former un recours constitutionnel subsidiaire quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de le faire (<ref-law>) et a un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). Le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>), lesquels constituent de toute façon les seuls griefs admissibles contre le refus de mesures provisionnelles (cf. <ref-law>; cf. arrêt 2C_376/2017 du 21 avril 2017 consid. 4). En vertu de l'<ref-law>, applicable par le renvoi de l'<ref-law>, les griefs tirés de la violation des droits fondamentaux doivent être invoqués et motivés par le recourant, à savoir expressément soulevés et exposés de manière claire et détaillée (cf. <ref-ruling> consid. 2.2 p. 232).
1.6. Dans le cadre d'un recours constitutionnel subsidiaire contre une décision de renvoi, le Tribunal fédéral a précisé que le recourant ne peut pas faire valoir des griefs en lien avec un droit de séjourner en Suisse (cf. <ref-ruling> consid. 1.1 p. 307; 2C_200/2017 du 14 juillet 2017 consid. 1.2.2; 2C_425/2010 du 17 août 2010 consid. 4; 2D_67/2009 du 4 février 2010 consid. 2.4 et 5). Seule peut être invoquée dans ce cadre la violation de droits constitutionnels spécifiques (protection de la vie humaine ou contre les traitements cruels, inhumains ou dégradants, etc.) ou la violation de droits de parties dont le manquement équivaut à un déni de justice formel (cf. <ref-ruling> consid. 3.3 p. 310. Cette jurisprudence se fonde sur l'impossibilité juridique de remettre en cause, dans le cadre du renvoi, une décision sur le droit de séjourner en Suisse rendue préalablement et entrée en force. En revanche, lorsque, comme en l'espèce, le renvoi a été prononcé sans décision préalable sur le droit de séjour, le recourant peut faire valoir dans le cadre du renvoi la violation de droits constitutionnels propres à lui conférer un droit de séjour en Suisse. Ceci vaut a fortiori lorsque le litige porte sur l'effet suspensif au renvoi.
1.7. En l'occurrence, le recourant invoque les art. 14 Cst. et 12 CEDH relatifs au droit au mariage et considère qu'il a le droit de demeurer en Suisse pendant la procédure préparatoire au mariage.
Devant le Tribunal cantonal, le recourant a produit des pièces confirmant qu'une procédure préparatoire au mariage était en cours et indiquant qu'une demande d'autorisation de séjour avait été déposée dans le canton de Genève, laquelle était à l'examen. Il en découle qu'on n'est pas en présence d'une situation où une décision relative au droit de séjour a été rendue préalablement au renvoi. Le recourant peut donc invoquer les art. 14 Cst. et 12 CEDH dans le cadre de la présente procédure relative à la restitution de l'effet suspensif au renvoi.
1.8. Au surplus, le recours a été déposé en temps utile (<ref-law> par le renvoi de l'<ref-law>) et dans les formes prescrites (art. 42 al. 1 et 2 LTF). Le recours, compris comme un recours constitutionnel subsidiaire, est partant recevable et il convient d'entrer en matière.
2.
2.1. Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été retenus en violation d'un droit constitutionnel (art. 118 al. 2 et 116 LTF), ce que le recourant doit invoquer avec précision (<ref-law> applicable par le renvoi de l'<ref-law>; cf. arrêt 2C_759/2017 du 16 mai 2018 consid. 2). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>, applicable par le renvoi de l'<ref-law>).
2.2. En tant que le recourant indique que, postérieurement à l'arrêt entrepris, la personne avec laquelle il envisage de se marier a obtenu un permis de séjour ainsi qu'une autorisation de travail, ce fait nouveau ne peut pas être pris en compte. Le Tribunal fédéral statuera sur la base des faits établis par l'autorité précédente.
3.
Le litige porte uniquement sur le point de savoir si c'est à bon droit que le Tribunal cantonal a confirmé le refus de restituer l'effet suspensif à la décision de renvoi du Service cantonal du 11 septembre 2017. Le recourant estime que cette décision viole le droit au mariage consacré aux art. 14 Cst. et 12 CEDH.
3.1. Les autorités compétentes rendent une décision de renvoi ordinaire à l'encontre d'un étranger qui n'a pas d'autorisation alors qu'il y est tenu (art. 64 al. 1 let. a LEtr). Le recours dirigé contre une telle décision n'a pas d'effet suspensif; l'autorité de recours peut toutefois le restituer (cf. art. 64 al. 3 LEtr; cf. arrêt 2C_819/2016 du 14 novembre 2016 consid. 2.1).
Savoir si dans un cas concret l'effet suspensif doit être restitué suppose une pesée des intérêts en présence (cf. <ref-ruling> consid. 3 p. 289; arrêts 2C_819/2016 du 14 novembre 2016 consid. 2.2; 2C_293/2013 du 21 juin 2013 consid. 4.1 non publié in <ref-ruling>). La restitution de l'effet suspensif est subordonnée à l'existence de justes motifs, qui résident dans un intérêt public ou privé prépondérant à ce qu'il soit renoncé à l'exécution immédiate de la décision (cf. arrêts 2C_1161/2013 du 27 février 2014 consid. 5.5; 2C_293/2013 du 21 juin 2013 consid. 4.1 non publié in <ref-ruling>).
En matière de décision de renvoi, la LEtr fait du retrait de l'effet suspensif la règle et sa restitution l'exception (cf. arrêt 2C_819/2016 du 14 novembre 2016 consid. 2.2). Cela ne signifie pas que seuls des motifs exceptionnels pourraient justifier la restitution de l'effet suspensif. Ce qui est déterminant est qu'il existe des motifs suffisamment importants justifiant de renoncer à l'exécution immédiate de la décision de renvoi (cf. arrêt 2C_819/2016 du 14 novembre 2016 consid. 2.2). Plus l'atteinte est grave pour le recourant, plus il y a de raisons de restituer l'effet suspensif (cf. arrêt 2C_819/2016 du 14 novembre 2016 consid. 2.2).
L'autorité dispose d'une importante liberté d'appréciation lorsqu'elle procède à la pesée des intérêts. En cas de recours contre une décision refusant la restitution de l'effet suspensif, le Tribunal fédéral contrôle seulement si l'autorité intimée a commis un excès ou un abus de son pouvoir d'appréciation (cf. <ref-ruling> consid. 3 p. 289; arrêt 2C_293/2013 du 21 juin 2013 consid. 4.1 non publié in <ref-ruling>). Il n'annule sa décision que si elle a négligé des intérêts essentiels, si de tels intérêts ont été appréciés de manière manifestement fausse, ou encore si la solution adoptée aboutit à préjuger de manière inadmissible du sort de la cause, ce qui empêcherait une bonne application du droit fédéral (cf. <ref-ruling> consid. 3 p. 289; arrêt 1C_88/2009 du 31 août 2009 consid. 3.1).
3.2. Un étranger en situation irrégulière en Suisse, peut, à certaines conditions, déduire du droit au mariage garanti par l'art. 14 Cst. et l'art. 12 CEDH un droit à pouvoir séjourner en Suisse en vue de s'y marier (cf. <ref-ruling> consid. 3.5 p. 356 ss).
La jurisprudence a cependant régulièrement relevé, dans le cadre du contrôle de la détention en vue du renvoi, que les projets de mariage ne s'opposent en principe pas à l'exécution d'une mesure de renvoi -et à la détention en vue de garantir celle-ci (cf. arrêts 2C_481/2017 du 15 décembre 2017 consid. 2.3; 2C_218/2013 du 26 mars 2013 consid. 5.2; 2C_150/2012 du 14 février 2012 consid. 2.2.2). Elle admet toutefois qu'il peut en aller autrement lorsque tous les papiers nécessaires en vue du mariage sont réunis, qu'une date de mariage a été fixée et que l'intéressé peut compter sur la délivrance d'une autorisation de séjour à brève échéance. Dans ces conditions, la détention en vue du renvoi peut en effet s'avérer disproportionnée et partant inadmissible (cf. arrêts 2C_481/2017 du 15 décembre 2017 consid. 2.3 et 4; 2C_218/2013 du 26 mars 2013 consid. 5.2; 2C_756/2009 du 15 décembre 2009 consid. 2.3.2 et les arrêts cités).
3.3. Il peut être renvoyé aux critères susmentionnés pour déterminer si l'autorité pouvait en l'espèce refuser de restituer l'effet suspensif au recours formé contre la décision de renvoi prononcée le 11 septembre 2017 à l'encontre du recourant. En effet, si ces critères étaient réunis, il faudrait envisager que l'intérêt du recourant à demeurer en Suisse puisse l'emporter sur l'intérêt à l'exécution immédiate de la décision de renvoi. C'est du reste ce que le Tribunal cantonal a admis, puisqu'il a considéré que les projets de mariage du recourant pourraient éventuellement constituer un obstacle à son renvoi et partant justifier l'octroi de l'effet suspensif au recours, dès lors qu'une procédure de mariage était effectivement en cours et qu'une demande d'autorisation de séjour en vue de célébrer l'union avait été déposée dans le canton de Genève et était encore à l'examen.
Selon les faits de l'arrêt entrepris, au moment où le Tribunal cantonal a statué, une date de mariage n'avait pas encore été fixée et l'issue de la procédure sur l'autorisation de séjour du recourant à Genève était incertaine. Le Tribunal cantonal pouvait ainsi en déduire que le mariage ne pouvait être considéré comme imminent. Dans ces conditions, il pouvait, sans violer les art. 14 Cst. et 12 CEDH, conclure qu'il n'existait pas de motifs prépondérants justifiant de restituer l'effet suspensif au recours. Il n'avait pas en sus à examiner, contrairement à ce que semble penser le recourant, si les conditions à l'octroi d'une autorisation de séjour à Genève étaient réunies, cette question relevant d'une procédure distincte. Il s'ensuit que l'arrêt entrepris n'est pas critiquable. Le recours, envisagé comme un recours constitutionnel subsidiaire, ne peut donc qu'être rejeté.
4.
Sur le vu de ce qui précède, le recours, envisagé comme un recours constitutionnel subsidiaire, doit être rejeté. Celui-ci étant d'emblée dénué de chances de succès, la requête d'assistance judiciaire doit être rejetée (<ref-law>). Succombant, le recourant devrait en principe supporter les frais judiciaires (art. 66 al. 1 première phrase LTF). Compte tenu des circonstances, il se justifie cependant de statuer sans frais (art. 66 al. 1 deuxième phrase LTF). Aucun dépens ne sera alloué (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours, envisagé comme un recours constitutionnel subsidiaire, est rejeté.
2.
La demande d'assistance judiciaire est rejetée.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Service des migrations, au Département de l'économie et de l'action sociale et au Tribunal cantonal de la République et canton de Neuchâtel, Cour de droit public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 6 août 2018
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber