Faits:
A. Le 22 juillet 2008, la Cheffe du Département de la formation, de la jeunesse et de la culture du canton de Vaud (ci-après: le Département) a rejeté le recours de X._ contre la décision du Conseil de direction de la Haute école pédagogique du canton de Vaud (ci-après la HEP) du 7 février 2008, qui prononçait l'expulsion de l'intéressé de la HEP. Cette décision a été envoyée le même jour sous pli recommandé, à l'adresse habituelle du recourant en Suisse, et indiquait qu'elle pouvait faire l'objet d'un recours auprès du Tribunal fédéral dans le délai de trente jours dès sa notification.
Par acte du 22 août 2008, déposé dans un bureau de poste français le 15 septembre 2008, X._ a formé un recours auprès du Tribunal fédéral qui, par arrêt du 28 octobre 2008 (2D_101/2008), l'a déclaré irrecevable et a transmis l'affaire au Tribunal cantonal (Cour de droit administratif et public) comme étant l'objet de sa compétence.
B. Par décision du 12 février 2009, le Juge instructeur du Tribunal cantonal a aussi déclaré le recours irrecevable, mais pour cause de tardiveté. Appliquant la loi sur le Tribunal fédéral du 17 juin 2005 (LTF) et la jurisprudence y relative, il a retenu en bref qu'en raison de la notification de la décision attaquée durant les féries (<ref-law>), le délai de recours avait commencé à courir le 16 août 2008 et arrivait à échéance le 15 septembre 2008 (<ref-ruling> consid. 4.2 p. 148). Posté à l'étranger le dernier jour du délai, le recours ne respectait pas l'<ref-law>, car il n'avait pu être pris en charge par la poste suisse qu'après l'échéance du délai de trente jours et n'était ainsi par- venu au Tribunal fédéral que le 18 septembre 2008.
Le 20 février 2009, X._ a indiqué son intention de former un recours auprès du Tribunal fédéral contre la décision d'irrecevabilité du 12 février 2009 et a présenté une demande d'assistance judiciaire complète.
Par lettre présidentielle du 3 mars 2009, le recourant a été informé de l'obligation d'élire en Suisse un domicile de notification (<ref-law>) et des conditions d'octroi de l'assistance judiciaire (<ref-law>).
Il lui était également indiqué que son acte du 20 février 2009 ne suffisait pas pour ouvrir un dossier.
X._ a complété son recours par acte du 28 février 2009, déposé le 12 mars 2009 dans un bureau de poste genevois, et a produit plusieurs pièces. Il conclut à la nullité de la décision du Juge instructeur du Tribunal cantonal du 12 février 2009, ainsi qu'à celle de la Cheffe du Département du 22 juillet 2008, pour absence de notification régulière, et se plaint d'une violation des art. 6 et 14 CEDH (principe de l'égalité des armes et interdiction de discrimination).
Le Juge instructeur du Tribunal cantonal et le Conseil de direction de la HEP ont renoncé à déposer des observations. Le Département a conclu à l'irrecevabilité du recours, subsidiairement à son rejet dans la mesure où il serait recevable.

Considérant en droit:
1. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1 p. 3). L'intéressé n'a pas indiqué expressément par quelle voie de recours il voulait procéder au Tribunal fédéral. Toutefois, cette imprécision ne saurait lui nuire si son mémoire peut être considéré comme un recours remplissant les conditions de la voie de droit qui lui est ouverte (cf. <ref-ruling> consid. 1.2 p. 302 s.).
1.1 Pour évaluer la recevabilité du recours contre une décision d'irrecevabilité, il faut tenir compte de l'objet du litige qui aurait dû être examiné si le Tribunal cantonal était entré en matière quant au fond, soit la décision d'exclusion du recourant de la HEP, pour fraude lors d'une procédure d'évaluation et en raison du comportement de l'intéressé durant sa formation. Il s'agit donc d'une décision d'élimination d'un programme d'études directement en lien avec une évaluation des capacités de l'étudiant évincé qui tombe sous le coup de l'art. 83 let. t LTF (cf. arrêts 2D_142/2008 du 23 avril 2009, consid. 1.2; 2D_62/2008 du 21 août 2008 au sujet d'une élimination pour plagiat et 2C_313/2007 du 21 août 2007 consid. 2.2). Il s'ensuit que le présent recours n'est pas recevable comme recours en matière de droit public. Dans la mesure où le recourant invoque la violation de droits constitutionnels (art. 6 et 14 CEDH: principe de l'égalité des armes et inter- diction de discrimination), il y a lieu toutefois d'examiner si son acte peut être traité comme recours de droit constitutionnel subsidiaire.
1.2 La voie du recours constitutionnel subsidiaire n'est ouverte que pour se plaindre de la violation des droits constitutionnels (<ref-law>), qu'il appartient au recourant d'invoquer et de motiver sous peine d'irrecevabilité (cf. <ref-law> applicable par renvoi de l'<ref-law>). Ce recours n'est recevable que contre les décisions finales (<ref-law>). Tel est le cas, en l'espèce, de la décision du Juge instructeur du Tribunal cantonal du 12 février 2009, qui constate l'irrecevabilité du recours de X._ du 15 septembre 2008 pour cause de tardiveté, mettant ainsi fin à l'instance. Le présent recours n'est donc recevable que dans cette mesure. Il est en revanche irrecevable, en tant qu'il porte sur la décision du 22 juillet 2008 elle-même, qui confirmait l'expulsion de la HEP.
1.3 Déposé en temps utile (<ref-law>), par le recourant qui a un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>), le recours est dès lors recevable sur les griefs dûment motivés conformément à l'<ref-law> (<ref-ruling> consid. 3.2 p. 88; <ref-ruling> consid. 1.4.2 p. 254; <ref-ruling> consid. 6 p. 397).
2. Le recourant n'a pas indiqué de domicile de notification en Suisse, bien qu'il ait été dûment informé de cette obligation, par lettre du 3 mars 2009.
2.1 Selon l'<ref-law>, les parties domiciliées à l'étranger doivent élire un domicile de notification. A défaut, le Tribunal fédéral peut s'abstenir de leur adresser des notifications ou les publier dans une feuille officielle.
Lorsqu'une partie a été avisée de la nécessité de fournir un domicile en Suisse, cette disposition laisse le choix au Tribunal fédéral, soit de notifier l'arrêt sous forme de publication dans une feuille officielle, soit de renoncer à toute notification, le cas échéant en informant par écrit la partie qu'un arrêt la concernant a été rendu (Florence Aubry Girardin, in Commentaire de la LTF, Berne 2009, n. 22 ad art. 39).
2.2 Il est vrai qu'en l'espèce, le recourant a indiqué son adresse électronique sur ses actes de recours des 20 et 28 février 2009 et a utilisé celle-ci dans sa correspondance avec la chancellerie du Tribunal fédéral du 12 mars 2009. Cette simple indication ne saurait toutefois être considérée comme une acceptation de la notification électronique au sens de l'<ref-law>, qui primerait sur le domicile de notification en Suisse de l'<ref-law>, car le recourant n'a pas fait de requête dans ce sens et n'a pas davantage fourni de clé cryptographique publique au Tribunal fédéral permettant de coder l'arrêt de manière à ce qu'il soit le seul lecteur possible (cf. art. 39 al. 2 et 60 al. 3 LTF). L'adressage de l'arrêt par voie électronique étant ainsi exclu, l'arrêt ne sera pas notifié au recourant, faute de domicile de notification en Suisse; ce dernier pourra toutefois être informé par écrit que le présent arrêt a été rendu.
3. Le recourant se plaint d'une violation du principe de l'égalité des armes, au sens de l'art. 6 § 1 CEDH, à propos de la notification de la Cheffe du Département du 22 juillet 2008 et des conséquences qu'en a tirées le Juge instructeur dans la décision attaquée, qui seules peuvent être examinées dans le présent recours (cf. supra consid. 1.2 ).
En l'espèce, le Juge instructeur du Tribunal cantonal a retenu à juste titre que la décision de la Cheffe du Département a été notifiée pendant les féries allant du 15 juillet au 15 août inclusivement (<ref-law>). Dans un tel cas, la jurisprudence considère que le délai de recours a bien commencé à courir le lendemain, soit le 16 août 2008 (<ref-ruling> consid. 4.2 p. 158). Le délai de trente jours de l'<ref-law> arrivait donc à échéance le dimanche 14 septembre, reporté au lundi 15 septembre 2008 (<ref-law>).
Quant à la communication de cette décision, le Juge instructeur pouvait admettre qu'elle avait été valablement notifiée en Suisse, à l'adresse indiquée par le recourant. Le Département n'avait en effet aucune obligation de renseigner le recourant sur les règles particulières relatives à l'exercice formel du droit de recours, comme s'il avait été domicilié à l'étranger, puisqu'il n'avait pas averti l'autorité administrative d'un déménagement à l'étranger, mais avait encore précisé, en annonçant son absence d'un mois, que "l'adresse à Lausanne est toujours en vigueur à fin d'expédition" (voir courrier électronique du 4 juillet 2008). A cet égard, le recourant ne peut donc rien tirer de l'<ref-ruling> consid. 4 p. 68, ni de l'adresse à Montpellier qu'il avait mentionnée sur sa demande d'admission à la HEP en 2007.
Dans ces conditions, on ne voit pas en quoi le recourant aurait été prétérité par la notification à son ancien domicile en Suisse, ce d'autant plus qu'en raison de la prolongation du délai de recours pendant les féries judiciaires, il a encore disposé d'un délai de recours de cinq semaines après son retour de l'étranger, fixé selon ses dires au 7 août 2008 (voir courrier électronique adressé au Département le 24 juillet 2008). Le délai de recours étant ainsi supérieur au délai usuel de trente jours de l'<ref-law>, le recourant ne saurait prétendre qu'il n'a pas eu droit à un procès équitable au sens de l'art. 6 § 1 CEDH.
4. 4.1 Le recourant invoque encore l'interdiction de la discrimination des justiciables en raison de leur nationalité découlant de l'art. 14 CEDH, principe également consacré à l'art. 8 al. 2 Cst. Il se réfère, en particulier, à la différence de traitement opérée entre les offices postaux situés au Liechtenstein, par rapport à ceux des autres pays limitrophes.
4.2 Le Juge instructeur du Tribunal cantonal a appliqué l'<ref-law>, qui dispose que les mémoires doivent être remis au plus tard le dernier jour du délai, soit au Tribunal fédéral soit, à l'attention de ce dernier, à La Poste Suisse ou à une représentation diplomatique ou consulaire suisse. Pour que le délai soit sauvegardé en cas de remise d'un mémoire à un office postal étranger, il faut que le pli contenant le mémoire arrive le dernier jour du délai au plus tard au greffe du Tribunal fédéral ou que la Poste Suisse en prenne possession avant l'expiration du délai (arrêt 4A_258/2008 du 7 octobre 2008, consid. 2; Kathrin Amstutz/Peter Arnold, Commentaire bâlois, Bundesgerichtsgesetz, n. 10 ad art. 48; Yves Donzallaz, Commentaire de la loi sur le Tribunal fédéral, n. 1238; voir également Jean-Maurice Frésard, in Commentaire de la LTF, Berne 2009, n. 11 ad art. 48). Le Tribunal fédéral a jugé qu'une application stricte de cette règle se justifie précisément pour des questions d'égalité de traitement et ne constitue pas un formalisme excessif (<ref-ruling> consid. 1 p. 67). Quant à l'exception prévue pour le Liechtenstein, elle n'institue pas une discrimination par rapport aux autres Etats, mais résulte de la collaboration particulière et des liens étroits qu'entretiennent la poste de ce pays avec la poste suisse, ainsi que les prévoient les accords internationaux (voir Echange de notes du 4 mars 1999 entre le Conseil fédéral suisse et le Gouvernement de la principauté de Liechtenstein: RS 0.783.595.14; arrêt 2C_754/2008 du 23 décembre 2008 consid. 2.3). Il s'agit donc, pour les tribunaux, d'appliquer une convention internationale. Dans l'arrêt précité, le Tribunal fédéral a ainsi confirmé qu'un recours déposé le dernier jour du délai dans un bureau de poste allemand devait être considéré comme tardif, dès lors qu'il n'existait pas de règles similaires à celles liant la Suisse et le Liechtenstein.
4.3 Il s'ensuit que la décision attaquée ne consacre nullement une discrimination du recourant, en considérant, sur la base des principes jurisprudentiels précités, que la remise du recours du 22 août 2008 à un bureau de poste français le dernier jour du délai pour recourir était tardive.
5. 5.1 Au vu de ce qui précède, le recours doit être rejeté dans la mesure de sa recevabilité.
5.2 Le recourant a déposé une demande d'assistance judiciaire complète pour la procédure devant le Tribunal fédéral. Compte tenu de l'absence de chances de succès de son recours quant à l'application des règles de procédure, sa demande doit être rejetée (<ref-law>). Il y a lieu donc de mettre les frais à la charge du recourant (<ref-law>), en tenant toutefois compte de sa situation financière (<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 demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
4. Le présent arrêt n'est pas notifié au recourant qui en est seulement avisé par écrit.
5. Le présent arrêt est communiqué au Conseil de direction de la Haute école pédagogique, à la Cheffe du Département de la formation et de la jeunesse et au Juge instructeur de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud.
Lausanne, le 22 juin 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Rochat