Faits:
A. Par jugement du 13 janvier 2003, le Tribunal d'arrondissement valaisan a notamment condamné G._, né en 1959, ressortissant espagnol, pour instigation à brigandage (simple), complicité d'escroquerie et instigation à incendie intentionnel (qualifié) à une peine de cinq ans de réclusion, sous déduction de la détention préventive.
Statuant sur appel le 14 novembre 2003, la Cour pénale II du Tribunal cantonal du Valais a réformé ce jugement en ce sens qu'elle a reconnu G._ coupable d'instigation à incendie simple (et non qualifié) et qu'elle l'a libéré du chef d'accusation de complicité d'escroquerie. En conséquence, elle a réduit la peine infligée à G._ à deux ans de réclusion.
B. S'agissant de la condamnation pour instigation à brigandage (simple), l'arrêt attaqué retient ce qui suit:
Z._ et B._, employés de la succursale de Sierre de la Banque cantonale du Valais, étaient chargés d'apporter, deux fois par semaine, au bureau de la poste de Sierre l'argent destiné notamment à la Banque nationale suisse. Informé de ce fait, D._ a pris contact avec deux amis, F._ et G._. D._ et F._ ont effectué des repérages pour vérifier l'exactitude des renseignements donnés par leur informateur. G._ a, pour sa part, déclaré pouvoir trouver deux exécutants. Il a pris contact avec X._, à qui il a expliqué qu'il avait un travail facile consistant à arracher un sac qui contenait l'argent d'une banque. X._ a consenti à participer à ce braquage et a demandé à K._ de le seconder. G._ a informé D._ du résultat de ses démarches.
Un premier contact a eu lieu sur le parking du restoroute de Villette-Jordillon. Y ont participé G._, F._, D._, X._ et K._. La discussion a porté sur les modalités de l'agression et sur la répartition des tâches et du butin. Un mois et demi plus tard, G._ a averti X._ que tout était prêt.
Le 17 avril 1997, D._ a amené K._ et X._ sur les lieux pour procéder aux derniers repérages. D._ et F._ devaient attendre un peu à l'écart, alors que K._ et X._ attaquaient les deux convoyeurs. Vers 15h45, ils se sont dirigés vers la banque. D._ a donné à K._ un appareil produisant des décharges électriques et un spray au poivre à X._. Lorsque les deux convoyeurs sont sortis de l'immeuble, X._ a bondi hors de l'immeuble avec son spray et K._ a frappé B._ à la tête, avec son appareil électrique, lui arrachant le sac rempli d'argent. Les deux agresseurs ont rejoint ensuite la voiture de D._ et se sont enfuis.
Arrivés dans un parking, les quatre acolytes ont partagé le butin. Le sac contenait 122'000 francs et 4'500 US$ ainsi que divers objets. D._ et F._ ont gardé 60'000 francs et les deux autres, à savoir K._ et X._, ont reçu le reste. Quelques jours plus tard, X._ a remis à G._ 20'000 francs; D._ et F._ ont pour leur part versé 10'000 francs à leur informateur.
C. G._ se pourvoit en nullité au Tribunal fédéral. Invoquant une violation de l'<ref-law> (instigation) ainsi que des art. 41 et 64 CP, il conclut à l'annulation de l'arrêt attaqué. En outre, il sollicite l'octroi de l'effet suspensif.

Le Tribunal fédéral considère en droit:
1. Saisi d'un pourvoi en nullité, le Tribunal fédéral contrôle l'application du droit fédéral (art. 269 PPF) sur la base exclusive de l'état de fait définitivement arrêté par l'autorité cantonale (cf. art. 277bis et 273 al. 1 let. b PPF). Le raisonnement juridique doit se fonder sur les faits retenus dans la décision attaquée, dont le recourant ne peut s'écarter. Le Tribunal fédéral n'est pas lié par les motifs invoqués, mais il ne peut aller au-delà des conclusions du recourant (art. 277bis PPF). Celles-ci, qui doivent être interprétées à la lumière de leur motivation, circonscrivent les points litigieux (<ref-ruling> consid. 1 p. 66).
2. Le recourant soutient qu'il s'est rendu coupable de complicité de brigandage et non d'instigation à brigandage. Selon lui, son activité a consisté essentiellement à apporter son soutien à D._ et à F._ en trouvant une personne intéressée et à la mettre en relation avec eux.
2.1 Selon l'<ref-law>, est instigateur "celui qui aura intentionnellement décidé autrui à commettre un crime ou un délit". L'instigation consiste à susciter chez autrui la décision de commettre un acte déterminé. La décision de l'instigué de commettre l'acte doit résulter du comportement incitatif de l'instigateur. Il faut donc un rapport de causalité entre ces deux éléments. Il n'est pas nécessaire que l'instigateur ait à vaincre la résistance de l'instigué. La jurisprudence admet que la volonté d'agir peut être déterminée même chez celui qui est disposé à agir ou chez celui qui s'offre à accomplir un acte réprimé par le droit pénal et cela aussi longtemps que l'auteur ne s'est pas encore décidé à passer à l'action concrètement (<ref-ruling> consid. 2a p. 14 s.; <ref-ruling> consid. 2b/aa p. 127 s.; <ref-ruling> consid. 2c p. 37 s.).
La peine applicable à l'instigateur est celle que la loi prévoit pour l'auteur de l'infraction. L'instigateur contribue en effet à l'obtention du résultat en amenant un tiers en renfort pour la réussite de l'entreprise criminelle et prend ainsi une part essentielle à la préparation du délit, à la décision de le commettre, ainsi qu'à l'établissement du plan; il se situe au même niveau que le coauteur du point de vue de sa culpabilité. En revanche, la culpabilité du complice, qui ne fait que prêter assistance à l'auteur principal (<ref-law>), sera moindre. Le juge pourra donc atténuer la peine du complice conformément au barème de l'<ref-law>, auquel renvoie l'<ref-law>.
2.2 Selon les constatations cantonales, le recourant a indiqué à X._ l'opportunité de commettre une infraction pouvant lui permettre d'obtenir de l'argent facilement. Ce faisant, il n'a pas seulement porté assistance à D._, mais a en outre éveillé chez X._ la conscience et la volonté de commettre une infraction. C'est donc à juste titre que l'autorité cantonale a retenu que le recourant s'était rendu coupable d'instigation au brigandage et non seulement de complicité. Il est sans importance que le recourant ait eu à faire à un criminel endurci et qu'il se soit contenté de lui signaler une opportunité de commettre une infraction. La jurisprudence n'exige pas en effet que l'instigateur fasse preuve d'une grande force de persuasion. En l'occurrence, X._ n'avait pas déjà pris la décision de passer à l'acte; du moins l'arrêt attaqué ne le retient pas. En lui proposant de braquer les deux convoyeurs, le recourant l'a donc bien décidé à commettre une infraction. Si le manque de résistance chez X._ ne saurait exclure l'application de l'<ref-law>, il pourra jouer en revanche un rôle lors de la fixation de la peine.
Contrairement à ce que semble croire le recourant, le fait qu'il a en outre participé en qualité d'interprète aux discussions entre D._, F._, K._ et X._, qu'il a transmis aux auteurs que tout était prêt et qu'il a ensuite touché un montant pour sa participation ne saurait diminuer sa responsabilité et faire de lui un complice. Au contraire, on pourrait se demander si, au vu de l'ensemble de ces actes, l'autorité cantonale n'aurait pas dû le considérer comme un coauteur. Cette question peut cependant rester indécise vu l'interdiction de la reformatio in pejus. Enfin, la condamnation de l'informateur au titre de complice est sans aucune incidence sur celle du recourant. D'une part, toute comparaison est difficile vu que les circonstances sont différentes. D'autre part, la jurisprudence a toujours affirmé la primauté du principe de la légalité sur le principe de l'égalité. Il ne suffirait donc pas que la loi ait été mal appliquée dans un cas pour prétendre à un droit à l'égalité dans l'illégalité (<ref-ruling> consid. 2c p. 47).
Mal fondés, les griefs du recourants doivent dès lors être rejetés.
3. Le recourant invoque en outre une violation de l'<ref-law>.
3.1 Se référant à l'<ref-ruling>, il reproche en premier lieu à l'autorité cantonale de ne pas avoir examiné si une peine assortie du sursis ne favoriserait pas mieux sa réinsertion.
Selon la jurisprudence, lorsque la peine privative de liberté qu'il envisage de prononcer n'est pas d'une durée nettement supérieure à 18 mois et que les conditions du sursis sont par ailleurs réunies, le juge doit examiner si, compte tenu de la situation personnelle de l'accusé, l'exécution de la peine n'irait pas à l'encontre du but premier du droit pénal, qui est de prévenir la commission d'infractions; le cas échéant, il doit en principe en tenir compte dans un sens atténuant dans le cadre de l'<ref-law> (<ref-ruling> consid. 2c p. 339 s.); encore faut-il cependant que la peine demeure proportionnée à la faute à sanctionner (<ref-ruling> consid. 2f p. 349 s.). S'agissant de la première de ces conditions, la jurisprudence a précisé qu'une peine privative de liberté n'est suffisamment proche de la limite de 18 mois permettant l'octroi du sursis que si elle n'excède pas 21 mois (<ref-ruling> consid. 3 p. 101). Cette condition n'est donc manifestement pas réalisée en l'espèce, puisque l'autorité cantonale envisageait d'infliger au recourant une peine de deux ans d'emprisonnement. Celle-ci n'avait dès lors pas à rechercher si une peine assortie du sursis ne favoriserait pas mieux la réinsertion du recourant. Mal fondé, le grief du recourant doit être rejeté.
3.2 Le recourant se plaint en outre de la violation de l'art. 64 avant-dernier alinéa CP, qui permet au juge d'atténuer la peine en application de l'<ref-law> à la double condition qu'un temps relativement long se soit écoulé depuis l'infraction et que le délinquant se soit bien comporté pendant ce temps.
Selon la jurisprudence, on peut considérer qu'un temps relativement long s'est écoulé seulement si la prescription de l'action pénale est près d'être acquise, c'est-à-dire si le jugement a été rendu à une date proche de celle où la prescription ordinaire serait intervenue (<ref-ruling> consid. 5 p. 209; <ref-ruling> consid. I p. 202 ss). Pour déterminer si l'action pénale est proche de la prescription, il faut se référer à la date à laquelle les faits ont été souverainement établis (<ref-ruling> consid. 3; <ref-ruling> consid. 5 p. 209). Pour les infractions commises avant l'entrée en force de la modification du code pénal du 5 octobre 2001 (<ref-law>), la période de référence correspond aux délais de l'art. 70 aCP.
D'après l'arrêt attaqué, l'attaque des convoyeurs de fonds de la Banque cantonale du Valais a eu lieu le 17 avril 1997, et l'incendie de Monthey s'est produit le 18 septembre 1996. Ces infractions remontent donc à environ sept ans avant le jugement de première instance et à huit ans avant le jugement sur appel. Selon l'ancien droit, la prescription ordinaire était de dix ans (cf. art. 140 et 221 CP; art. 70 aCP). Ce délai n'est donc de loin pas échu tant pour la première infraction que pour la seconde. En conséquence, le temps écoulé depuis les infractions reprochées n'est pas "relativement long" au sens de l'art. 64 avant-dernier alinéa CP. La première condition de cette circonstance atténuante n'étant pas réalisée, il n'y a pas lieu d'examiner la seconde et donc de déterminer si le recourant s'est bien comporté. Mal fondé, le grief du recourant doit être rejeté.
3.3 Le recourant invoque enfin la violation du principe de la célérité consacré par les art. 29 al. 1 Cst., 6 par. 1 CEDH et 14 par. 3 let. c Pacte ONU II.
3.3.1 Le principe de la célérité impose aux autorités, dès le moment où l'accusé est informé des soupçons qui pèsent sur lui, de mener la procédure pénale sans désemparer, afin de ne pas maintenir inutilement l'accusé dans les angoisses qu'elle suscite (<ref-ruling> consid. 2a p. 140). Il s'agit d'une exigence posée à l'égard des autorités pénales, qui se distingue de la circonstance atténuante du temps relativement long (art. 64 avant-dernier al. CP), liée à l'approche de la prescription et qui suppose que l'accusé se soit bien comporté dans l'intervalle (Wiprächtiger, Basler Kommentar, Strafgesetzbuch I, 2003, n. 31 ad art. 64). Comme les retards dans la procédure pénale ne peuvent être guéris, le Tribunal fédéral a fait découler de la violation du principe de la célérité des conséquences sur le plan de la peine. Le plus souvent, la violation de ce principe conduira ainsi à une réduction de la peine, parfois même à la renonciation à toute peine ou encore à une ordonnance de non-lieu (en tant qu'ultima ratio dans des cas extrêmes; <ref-ruling> consid. 4d p. 129; <ref-ruling> consid. 2a p. 140/141). La jurisprudence a ainsi créé praeter legem des sanctions autonomes de nature matérielle.
3.3.2 Selon la jurisprudence, la question de savoir si le principe de la célérité a été violé, qui relève de la violation directe de la Constitution et de la Convention, doit être invoquée dans un recours de droit public. En revanche, l'accusé qui veut se plaindre de ce que l'autorité cantonale n'a pas tiré les conséquences que le droit fédéral fait découler de la violation du principe de la célérité, en particulier sur le plan de la peine, doit agir par le biais du pourvoi en nullité, car la détermination des conséquences d'une violation du principe de la célérité sur l'interprétation et l'application du droit pénal fédéral relève d'une violation indirecte de la Constitution et de la Convention (<ref-ruling> consid. 1b p. 109; <ref-ruling> consid. 2a p. 141).
Cette jurisprudence ne précise cependant pas si, dans le cadre du pourvoi, la Cour de cassation pénale du Tribunal fédéral peut se prononcer, à titre préjudiciel, sur la violation du principe de la célérité ou si le recourant doit déposer au préalable un recours de droit public pour faire constater cette violation si celle-ci n'a pas déjà été constatée par l'autorité cantonale. Dans l'<ref-ruling>, le Tribunal fédéral a en effet examiné si la longueur de la procédure devait entraîner des sanctions particulières. Il n'est cependant pas entré en matière sur la question de savoir si l'autorité cantonale avait nié à tort la violation du principe de la célérité, question qui a été laissée ouverte dans un recours de droit public interjeté parallèlement (arrêt du Tribunal fédéral 6P.98/1992 du 19 mars 1993, consid. 3c ).
L'accusé peut certes obtenir la constatation simplement déclaratoire de la violation du principe de la célérité qui constitue déjà une forme de réparation (<ref-ruling> consid. 1.3 p. 417; <ref-ruling> consid. I.4 p. 111; arrêt du Tribunal fédéral du 23 octobre 2000, publié in Pra 90/2001 n° 3 p. 12, consid. 4e) ou demander des dommages-intérêts (<ref-ruling>), mais, en règle générale, le recourant qui fait grief à l'autorité cantonale d'avoir violé le principe de la célérité entend obtenir une réduction de la peine. Depuis une dizaine d'années, la violation du principe de la célérité est ainsi devenue, de fait, une circonstance atténuante de la peine à part entière.
Vu les relations étroites qui existent entre la question de la violation du principe de la célérité et l'application de l'<ref-law>, il apparaît dès lors inutilement compliqué, mais surtout artificiel, d'obliger l'accusé à déposer un recours de droit public pour faire constater la violation du principe de la célérité, puis un pourvoi pour obtenir une réduction de sa peine. Dans un tel cas, il faut admettre que la question de la violation du principe de la célérité puisse être traitée, dans le cadre d'un pourvoi, au titre de question préjudicielle à la question principale sur la fixation de la peine. L'accusé qui entend se plaindre que l'autorité cantonale n'a pas tenu compte de la violation du principe de la célérité lors de la fixation de la peine doit donc agir par la voie du pourvoi en nullité, sans égard au fait que l'autorité cantonale ait expressément admis ou nié la violation du principe de la célérité ou qu'elle ait ignoré la question (arrêt du Tribunal fédéral 6S.309/2001 du 23 août 2001 ).
Il s'ensuit que le grief du recourant est recevable, même si l'autorité cantonale n'a pas constaté formellement que le principe de la célérité avait été violé.
3.3.3 Le caractère raisonnable de la durée d'une procédure s'apprécie suivant les circonstances de la cause, lesquelles commandent généralement une évaluation globale, en tenant compte notamment de la complexité de l'affaire, du comportement de l'accusé et de celui des autorités compétentes (<ref-ruling> consid. 2c p. 142 et les références citées). Comme on ne peut pas exiger de l'autorité pénale qu'elle s'occupe constamment d'une seule et unique affaire, il est inévitable qu'une procédure comporte quelques temps morts. Lorsqu'aucun d'eux n'est d'une durée vraiment choquante, c'est l'appréciation d'ensemble qui prévaut; des périodes d'activités intenses peuvent donc compenser le fait que le dossier a été laissé momentanément de côté en raison d'autres affaires (<ref-ruling> consid. 2c p. 142). Selon la jurisprudence européenne, apparaissent comme des carences choquantes une inactivité de treize ou quatorze mois au stade de l'instruction, un délai de quatre ans pour qu'il soit statué sur un recours contre l'acte d'accusation, un délai de dix ou onze mois pour que le dossier soit transmis à l'autorité de recours (<ref-ruling> consid. 2c p. 144; <ref-ruling> consid. 1c p. 110). Le principe de la célérité peut être violé, même si les autorités pénales n'ont commis aucune faute; elles ne sauraient ainsi exciper des insuffisances de l'organisation judiciaire.
Le recourant estime que son affaire, qui remonte à 2000, aurait dû globalement être jugée plus rapidement. Il se plaint notamment du fait qu'il a dû attendre le début 2003 pour être présenté aux juges de première instance, alors que les faits le concernant auraient été établis et reconnus déjà deux mois après l'ouverture de l'action pénale à son encontre. Cette critique est infondée. Le dossier est relativement volumineux. L'enquête a été dirigée contre cinq accusés, qui ont commis des infractions variées (brigandage, incendie, escroquerie, faux dans les titres, etc.) et dont les rôles sont étroitement liés. Au vu de ces circonstances, une durée de trois ans entre l'ouverture de l'instruction et le jugement de première instance, puis d'une année entre le jugement de première instance et le jugement sur appel ne prête pas le flanc à la critique. Infondé, le grief du recourant doit donc être rejeté.
3.4 En définitive, dans le cadre du large pouvoir d'appréciation dont elle bénéficie en la matière, l'autorité cantonale a tenu compte de tous les éléments nécessaires et pertinents et n'en a omis aucun pour arrêter la peine qu'elle a prononcée à l'égard du recourant. Elle a motivé par ailleurs la peine de manière suffisante. Au regard, notamment, de la faute du recourant, la peine prononcée de deux ans de réclusion ne procède pas d'un abus du pouvoir d'appréciation. Le grief de violation de l'<ref-law> est dès lors infondé.
4. Au vu de ce qui précède, le pourvoi doit être rejeté.
Succombant, le recourant doit supporter les frais judiciaires (art. 278 al. 1 PPF; art. 156 al. 1 OJ).
Vu l'issue du pourvoi, la requête d'effet suspensif est devenue sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le pourvoi est rejeté.
2. Un émolument judiciaire de 2'000 francs est mis à la charge du recourant.
3. Le présent arrêt est communiqué en copie au mandataire du recourant, au Ministère public valaisan et au Tribunal cantonal du Valais, Cour pénale II.
Lausanne, le 22 avril 2004
Au nom de la Cour de cassation pénale
du Tribunal fédéral suisse
Le président: La greffière: