Faits:
A. Par jugement du 8 février 2008, le Tribunal de police de l'arrondissement de Lausanne a constaté que X._ s'était rendu coupable d'infraction à la Loi fédérale sur le séjour et l'établissement des étrangers et l'a condamné à la peine de quatre mois de privation de liberté, avec suite de frais.
B. Saisie d'un recours en réforme et en nullité, la Cour de cassation pénale du Tribunal cantonal vaudois l'a rejeté par arrêt du 11 avril 2008. Cet arrêt repose en substance sur les faits suivants.
B.a X._ est né le 1er janvier 1984 en Côte d'Ivoire, son pays d'origine. En juin 2003, il a déposé une demande d'asile en Suisse, laquelle a été rejetée par décision du 24 octobre 2003, définitive et exécutoire dès le 27 novembre 2003. Le renvoi de Suisse de X._ a été prononcé. Il n'a cependant jamais quitté la Suisse depuis lors, n'ayant aucun désir de retourner en Côte d'Ivoire, où, selon lui, la situation politique est instable et conduit ses ressortissants à vivre dans la crainte perpétuelle d'une arrestation arbitraire. L'intéressé n'est au bénéfice d'aucun titre de séjour valable et n'a aucune ressource. Il vit grâce à l'aide d'urgence accordée de quinzaine en quinzaine par le Service de la population. Il a expliqué vivre momentanément chez un ami à Yverdon-les-Bains. Son casier judiciaire comprend quatre inscriptions, pour des condamnations entre le mois d'avril 2004 et janvier 2006, principalement pour infractions à la LStup et à la LSEE.
Entre le 26 janvier 2006, date de sa dernière condamnation, et le 28 septembre 2007, X._ a continué de séjourner en Suisse sans aucune autorisation.
B.b En bref, la cour cantonale, examinant le grief de nullité soulevé par le recourant selon lequel il n'avait pas été valablement inculpé, a jugé que le recours en nullité fondé sur l'art. 411 let. g CPP/VD était irrecevable en tant qu'il avait trait à des irrégularités de procédure antérieures à l'ordonnance de clôture d'enquête. Le défaut d'inculpation ne constituait pas une violation d'une règle essentielle de la procédure au stade du jugement, mais uniquement à l'étape antérieure. Il aurait ainsi incombé au recourant de faire valoir ce moyen en exerçant un éventuel recours contre l'ordonnance de renvoi.
B.c Examinant ensuite les conclusions en réforme du recourant, la cour cantonale a estimé que l'aide d'urgence accordée pour des raisons humanitaires n'influençait en rien le statut en Suisse du recourant, si bien que son séjour demeurait illicite. L'aide humanitaire dont il bénéficiait ne s'opposait donc pas à sa condamnation.
Quant à la peine, la situation financière du recourant ne permettait pas le prononcé d'une peine pécuniaire. Son statut en Suisse ne permettait pas d'atteindre le but de resocialisation assigné au travail d'intérêt général, qui aurait en outre achoppé sur des problèmes pratiques au stade de l'exécution en raison de sa situation précaire. Le pronostic relatif au sursis était défavorable, en raison de cinq condamnations précédentes dont trois pour infraction à la LSEE et de l'intention manifestée de rester en Suisse et de prolonger son comportement illicite. Un sursis partiel n'entrait pas non plus en ligne de compte eu égard à la durée de la peine. Le prononcé d'une courte peine privative de liberté était donc justifié.
C. X._ forme un recours en matière pénale contre cet arrêt. Il conclut principalement à son annulation et au renvoi de la cause à l'autorité cantonale afin qu'elle rende une nouvelle décision, et, à titre subsidiaire, à sa réforme en ce sens qu'une peine pécuniaire de 120 jours-amende, à un franc l'un, lui soit infligée. Il requiert en outre d'être mis au bénéfice de l'assistance judiciaire et que l'effet suspensif soit restitué.
Le Ministère public et la Cour cantonale ont renoncé à déposer des observations.

Considérant en droit:
1. A titre principal, le recourant reproche à la cour cantonale d'avoir arbitrairement appliqué le droit cantonal. Il soutient, en résumé, n'avoir jamais été valablement inculpé, cet acte de procédure lui ayant été signifié non par le juge d'instruction, qui serait seul compétent pour y procéder en application des règles cantonales de procédure, mais par un greffier. Ce vice, qui serait essentiel, aurait dû conduire la cour cantonale à annuler le jugement de première instance en application de l'art. 411 let. g CPP/VD et non à déclarer le grief irrecevable.
1.1 Une décision est arbitraire lorsqu'elle est manifestement insoutenable, méconnaît gravement une norme ou un principe juridique clair et indiscuté, ou encore heurte de manière choquante le sentiment de la justice et de l'équité. Il ne suffit pas que sa motivation soit insoutenable; encore faut-il que la décision apparaisse arbitraire dans son résultat. A cet égard, le Tribunal fédéral ne s'écarte de la solution retenue que si celle-ci apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motif objectif ou en violation d'un droit certain. Il n'y a pas arbitraire du seul fait qu'une autre solution paraît également concevable voire même préférable (<ref-ruling> consid. 5.4 et les arrêts cités, p. 148, 129 I 8 consid. 2.1 p. 9).
1.2 Conformément à l'<ref-law>/VD, le recours en nullité prévu à l'article 410 est ouvert en raison d'irrégularités de procédure postérieures à l'arrêt ou à l'ordonnance de renvoi. La lettre g de cette disposition consacre un tel cas de nullité s'il y a eu violation d'une règle essentielle de procédure non mentionnée aux lettres a à f de cette disposition et que cette violation a été de nature à influer sur la décision attaquée.
En l'espèce, la cour cantonale a rejeté le moyen de nullité comme mal fondé. On comprend cependant à la lecture des considérants de la cour cantonale qu'elle a jugé le recours en nullité fondé sur l'art. 411 let. g CPP/VD irrecevable en tant que le recourant invoquait une irrégularité de procédure antérieure à l'ordonnance de clôture d'enquête. L'arrêt entrepris précise en effet que le défaut d'inculpation ne constituait pas une violation d'une règle essentielle de la procédure au stade du jugement, mais uniquement au stade de l'ordonnance de clôture d'enquête. Il appartenait ainsi au recourant, selon la cour cantonale, de faire valoir ce moyen en exerçant un éventuel recours contre l'ordonnance de renvoi, ce qu'il n'avait pas fait. Il ne pouvait dès lors plus s'en prévaloir à posteriori (arrêt entrepris, consid. II.1, p. 4).
1.3 Le recourant objecte qu'il ne pouvait pas recourir contre l'ordonnance de clôture d'enquête du 25 juillet 2007, dès lors qu'il s'agissait d'une ordonnance de condamnation qui avait été transformée en ordonnance de renvoi ensuite de son opposition.
1.3.1 Il ressort des pièces du dossier et du jugement de première instance que le recourant a fait l'objet d'une ordonnance de condamnation le 25 juillet 2007 dans l'enquête PE07.002674-CMI. Cette ordonnance portait sur une infraction à la LSEE reprochée au recourant pour la période du 26 janvier 2006 au 6 juin 2007. Le recourant y a fait opposition le 7 août 2007. Il a, ensuite, fait l'objet d'une ordonnance de renvoi le 5 novembre 2007 dans l'enquête PE07.015994-CMI. Cette ordonnance portait sur la même infraction pour la période du 7 juin au 28 septembre 2007. Lors de l'audience du 8 février 2008, le recourant a indiqué maintenir son opposition à l'ordonnance de condamnation du 25 juillet 2007 et le Tribunal d'arrondissement a joint les causes avant d'instruire et de juger.
1.3.2 Il s'ensuit que le recourant ne démontre pas en quoi il n'aurait pas été en mesure de faire valoir son défaut d'inculpation par la voie d'un recours dirigé contre l'ordonnance de renvoi du 5 novembre 2007, qui était ouvert en application de l'art. 294 let. f CPP/VD. On ne voit dès lors pas en quoi la cour cantonale aurait appliqué arbitrairement le droit cantonal de procédure en déclarant irrecevable son recours dirigé contre le jugement de première instance, en ce qui concerne sa condamnation pour être demeuré illégalement en Suisse du 7 juin au 28 septembre 2007. Le grief est infondé dans cette mesure.
1.3.3 L'ordonnance de condamnation du 25 juillet 2007 est devenue de lege ordonnance de renvoi ensuite de l'opposition formée par le recourant (cf. <ref-law>/VD). Selon la jurisprudence cantonale, le recours pour violation d'une règle essentielle de la procédure dirigé contre une ordonnance de condamnation à laquelle le condamné fait simultanément opposition est rendu sans objet par cette dernière parce que le renvoi consécutif à l'opposition permet à l'intéressé de faire valoir ses moyens devant le tribunal de police (BOVAY ET AL., Procédure pénale vaudoise, 3e éd. 2008, art. 294, n. 10.3.3). On ne saurait donc faire grief au recourant de n'avoir pas formé de recours déjà au stade de l'ordonnance de clôture d'enquête à laquelle il s'est opposé.
Le recourant précise toutefois dans ses écritures ne pas soutenir que le chef d'accusation retenu par le tribunal de première instance embrasserait des faits sur lesquels il n'aurait jamais été entendu ou qu'il n'aurait pas été en mesure de requérir des mesures d'instruction nécessaires ou utiles en raison des circonstances dans lesquelles son inculpation lui a été signifiée. En d'autres termes, le recourant soutient que le vice affectant l'inculpation justifierait l'annulation du jugement de première instance indépendamment de toute conséquence pratique sur l'exercice de ses droits. Or, l'<ref-law>/VD distingue des causes absolues et des causes relatives de nullité, ces dernières étant définies comme celles qui ont été de nature à influer sur le jugement (BOVAY ET AL. , op. cit., art. 411, n. 1.2), catégorie à laquelle ressortissent les irrégularités visées par l'art. 411 let. g CPP/VD invoqué par le recourant dans son recours cantonal. Dans la mesure où elle se résume à soutenir que « le défaut d'inculpation (valable) continue de constituer une violation d'une règle essentielle de la procédure au stade du jugement », l'argumentation du recourant, qui ne tente pas d'établir quelle influence l'irrégularité aurait eu sur le jugement de première instance, ne démontre pas que l'entrée en matière sur son grief aurait pu conduire à l'annulation du jugement de première instance. Il n'explique donc pas en quoi l'arrêt cantonal serait arbitraire dans son résultat. Le grief est donc infondé également en ce qui concerne les faits visés dans l'ordonnance de condamnation du 25 juillet 2007.
1.4 Pour le surplus, le recourant n'invoque expressément la violation d'aucune autre garantie constitutionnelle ou conventionnelle, d'aucune garantie de nature formelle en particulier, si bien qu'il n'y a pas lieu d'examiner la question sous cet angle (<ref-law>).
2. Le recourant conteste ensuite sa condamnation à une courte peine privative de liberté.
2.1 Selon la cour cantonale, eu égard à la date à laquelle les faits sont survenus et à celle où ils ont été jugés, trois règles fixant la peine étaient susceptibles d'entrer en ligne de compte. Dans sa teneur en vigueur jusqu'au 31 décembre 2006, l'art. 23 al. 1 LSEE permettait de sanctionner celui qui entre ou réside en Suisse illégalement de l'emprisonnement jusqu'à six mois, peine à laquelle pouvait s'ajouter une amende de 1000 francs au plus, cependant que les cas de peu de gravité pouvaient être sanctionnés d'une amende seulement. Dans la teneur modifiée de cette disposition en vigueur dès le 1er janvier 2007, cette infraction était sanctionnée d'une peine pécuniaire de 180 jours-amende au plus. Enfin, selon l'art. 115 al. 1 de la nouvelle loi fédérale sur les étrangers du 16 décembre 2005, en vigueur depuis le 1er janvier 2008, quiconque séjourne illégalement en Suisse, notamment après l'expiration de la durée du séjour non soumis à autorisation ou du séjour autorisé est puni d'une peine privative de liberté d'un an au plus ou d'une peine pécuniaire. De ces trois règles, celle en vigueur du 1er janvier au 31 décembre 2007 était la plus favorable, dès lors qu'elle prévoyait exclusivement une peine maximale de 180 jours, contre une peine de 180 jours pouvant être combinée avec une amende pour la loi la plus ancienne et une peine allant jusqu'à un an pour la loi actuelle.
2.2 Le recourant ne conteste pas le choix de la règle effectué par la cour cantonale conformément à l'<ref-law>. Il soutient en revanche que, l'art. 23 LSEE, dans sa teneur en vigueur du 1er janvier au 31 décembre 2007 ne permettrait pas le prononcé d'une peine privative de liberté.
Ce grief est fondé. Dans un arrêt récent, la cour de céans a, en effet déjà eu l'occasion de constater que faute d'une base légale explicite, l'art. 23 al. 1 LSEE dans sa version en vigueur du 1er janvier au 31 décembre 2007 ne permettait pas de prononcer une condamnation à une peine privative de liberté (<ref-ruling> consid. 8.4, p. 81). Il s'ensuit que l'arrêt cantonal, qui viole le droit fédéral sur ce point doit être annulé et la cause renvoyée à la cour cantonale afin qu'elle fixe à nouveau la peine. Ce faisant, la cour cantonale devra encore tenir compte des éléments suivants.
2.3 En ce qui concerne le choix de la sanction, il convient de relever, tout d'abord que selon les constatations de fait de l'arrêt entrepris, la demande d'asile en Suisse du recourant a été rejetée par décision définitive et exécutoire dès le 27 novembre 2003 et son renvoi a été prononcé (arrêt entrepris, consid. B.1, p. 2). Il s'ensuit que le prononcé d'un travail d'intérêt général n'entre pas en considération, cette sanction apparaissant d'emblée inadaptée (cf. <ref-ruling> consid. 3.3, 97 consid. 6.3.3.4, p. 110), sans qu'il soit nécessaire d'examiner plus avant le point de savoir si l'art. 23 al. 1 LSEE constitue une base légale suffisamment explicite au prononcé d'une telle sanction.
Quant à la quotité de la sanction, le Tribunal fédéral a, dans un arrêt récent, jugé que la peine infligée en application de l'art. 23 al. 1 LSEE devait tenir compte de précédentes condamnations déjà infligées à raison du même séjour illicite ininterrompu pour des périodes antérieures, de sorte que l'ensemble des peines cumulées n'excède pas la peine maximale prévue par la loi (arrêt du 4 novembre 2008 X c. Staatsanwaltschaft des Kantons Schaffhausen, 6B_114/2008 destiné à la publication aux ATF).
Enfin, selon la jurisprudence - à laquelle on renvoie en ce qui concerne les modalités générales de la fixation de la peine pécuniaire - les aides sociales constituent des revenus qui doivent être pris en considération lors de la fixation du montant du jour-amende. Même si le montant de ce revenu peut apparaître insuffisant pour garantir le minimum vital du droit des poursuites, cette circonstance ne s'oppose pas encore au prononcé d'une peine pécuniaire, mais doit être prise en considération en procédant, en tant que de besoin, à des abattements du revenu net déterminant (<ref-ruling> consid. 5, p. 65 ss; v. aussi arrêt 6B_541/2007, consid. 6).
3. Le recours est admis. Le recourant qui obtient gain de cause peut prétendre une indemnité de dépens (<ref-law>), si bien que sa demande d'assistance judiciaire est sans objet (<ref-law>). Il n'y a pas lieu de prélever des frais (<ref-law>).
La requête de restitution de l'effet suspensif est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. L'arrêt cantonal est annulé en tant qu'il confirme la condamnation du recourant à une peine privative de liberté et la cause renvoyée à l'autorité cantonale afin qu'elle complète l'instruction et rende une nouvelle décision au sens des considérants qui précèdent.
2. Le canton de Vaud versera au conseil du recourant une indemnité de 2'500 francs à titre de dépens.
3. La requête d'assistance judiciaire est sans objet.
4. Il n'est pas prélevé de frais.
5. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud, Cour de cassation pénale.
Lausanne, le 26 décembre 2008
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Le Greffier:
Schneider Vallat