Faits:
A. Le 3 octobre 2001, X._, ressortissant portugais né en 1975, qui avait déjà séjourné à trois reprises en Suisse en qualité de travailleur saisonnier entre juin 1998 et août 2000, a déposé une nouvelle demande d'autorisation de séjour.
Par décision du 20 mars 2002, le Service de la population du canton de Vaud (ci-après: le Service de la population) a rejeté la demande, au motif, notamment, que l'intéressé avait été condamné à dix jours d'emprisonnement avec sursis pour contravention à la loi fédérale du 3 octobre 1951 sur les stupéfiants et les substances psychotropes (Loi sur les stupéfiants, LStup; RS 812.121) et infraction à la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 142.20). X._ a recouru contre cette décision devant le Tribunal administratif du canton de Vaud (ci-après: le Tribunal administratif). Faute du paiement de l'avance de frais requise, son recours a été déclaré irrecevable (arrêt du 7 juin 2002). Le Service de la population lui a alors imparti un «délai immédiat» pour quitter le canton de Vaud (décision du 10 juin 2002).
B. A la suite de l'entrée en vigueur, le 1er juin 2002, de l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681; ci-après cité: Accord sur la libre circulation des personnes ou Accord ), X._ a demandé, le 13 juin 2002, que son cas soit reconsidéré à la lumière de cet accord.
Par décision du 18 juin 2003, le Service de la population a rejeté la demande de reconsidération. Saisi d'un recours contre cette décision, le Tribunal administratif l'a également rejeté. En bref, cette autorité a considéré que X._, sans travail et au bénéfice de l'aide sociale, ne disposait pas des moyens financiers suffisants pour assurer sa subsistance, ce qui le privait du droit d'obtenir une autorisation de séjour pour ressortissant communautaire «n'exerçant pas d'activité économique» ou «à la recherche d'un emploi» (arrêt du Tribunal administratif du 24 octobre 2003).
C. Agissant par la voie du recours de droit administratif, X._ demande au Tribunal fédéral d'annuler, sous suite de frais et dépens, l'arrêt précité du Tribunal administratif, en concluant à ce que le Service de la population soit invité à lui délivrer «une autorisation de séjour, cas échéant une autorisation de courte durée pour recherches d'emploi». Il requiert le bénéfice de l'assistance judiciaire gratuite pour le paiement des frais de justice. Pour l'essentiel, il fait valoir qu'une autorisation de séjour doit lui être accordée, vu sa qualité de travailleur communautaire ou, du moins, de ressortissant communautaire à la recherche d'un emploi. Il souligne que la précarité de sa situation actuelle n'est que provisoire et qu'il n'en est nullement responsable.
Le Tribunal administratif et le Service de la population se réfèrent aux considérants de l'arrêt attaqué. L'Office fédéral de l'immigration, de l'intégration et de l'émigration (ci-après: Office fédéral) conclut au rejet du recours.
D. Par ordonnance du 11 décembre 2003, le Président de la IIe Cour de droit public a accordé l'effet suspensif au recours.

Le Tribunal fédéral considère en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 227 et les références).
1.1 Selon l'art. 100 al. 1 lettre b ch. 3 OJ, le recours de droit administratif n'est pas recevable en matière de police des étrangers contre l'octroi ou le refus d'autorisations auxquelles le droit fédéral ne confère pas un droit. Selon l'art. 4 LSEE, les autorités compétentes statuent librement, dans le cadre des prescriptions légales et des traités avec l'étranger, sur l'octroi ou le refus d'autorisations de séjour ou d'établissement. En principe, l'étranger n'a pas droit à l'autorisation de séjour. Ainsi, le recours de droit administratif est irrecevable, à moins que ne puisse être invoquée une disposition particulière du droit fédéral ou d'un traité, accordant le droit à la délivrance d'une telle autorisation (<ref-ruling> consid. 1.1.1 p. 148 et les arrêts cités).
1.2 Sous réserve des dispositions transitoires - non pertinentes en l'espèce - de l'art. 10 ALCP, le droit de séjour et d'accès à une activité économique est garanti aux ressortissants d'un Etat membre de la Communauté européenne conformément aux dispositions de l'annexe I ALCP (art. 4 ALCP). Ainsi, les travailleurs salariés, les indépendants et les prestataires de services ont le droit de séjourner et d'exercer une activité économique selon les modalités prévues aux chapitres II à IV de l'annexe I ALCP (art. 2 par. 1 al. 1 annexe I ALCP). Mais les ressortissants communautaires ont aussi le droit, en principe, de se rendre en Suisse «pour y chercher un emploi et y séjourner pendant un délai raisonnable» (art. 2 par. 1 al. 2 annexe I ALCP). Enfin, ceux qui n'exercent pas d'activité économique et qui ne bénéficient pas d'un droit de séjour en vertu d'autres dispositions de l'Accord (rentiers, étudiants...) ont un droit de séjour pour autant qu'ils remplissent les conditions préalables requises dans le chap. V de l'annexe I ALCP (art. 2 par. 2 annexe I ALCP).
Quels que soient leur statut ou les motifs de leur demande d'autorisation de séjour, les ressortissants communautaires peuvent donc, en principe, du seul fait de leur appartenance nationale, invoquer une disposition de l'Accord sur la libre circulation des personnes (et son annexe I) pour faire valoir un droit de séjour en Suisse. Dans cette mesure, le motif d'irrecevabilité prévu à l'art. 100 al. 1 lettre b ch. 3 OJ ne leur est pas opposable s'ils recourent contre une décision leur refusant le droit de séjourner en Suisse, sans toutefois que cela ne préjuge en rien de l'issue du litige. C'est, en effet, un problème de fond que la question de savoir, dans un cas particulier, si la disposition invoquée leur confère effectivement le droit à une autorisation de séjour ou si, au contraire, une telle autorisation doit leur être refusée, en raison de l'inobservation d'une modalité ou d'une condition requise pour exercer le droit en cause (comme l'exigence, prévue à l'art. 24 par. 1 lettres a et b annexe I ALCP, de disposer de moyens financiers suffisants; cf. infra consid. 2.1) ou pour une autre raison, telle l'existence d'un motif d'ordre public (cf. art. 5 annexe I ALCP) ou la constatation d'un abus de droit (cf. <ref-ruling>).
Par conséquent, en sa seule qualité de ressortissant portugais, le recourant est recevable à recourir, au sens de l'art. 100 al. 1 lettre b ch. 3 OJ, indépendamment des motifs de sa demande d'autorisation de séjour et de son statut actuel en Suisse.
1.3 Pour le surplus, formé en temps utile et dans les formes prescrites, le recours est recevable.
2. 2.1 Les premiers juges ont considéré que X._ ne pouvait pas obtenir un titre de séjour pour «personne n'exerçant pas une activité économique» (cf. chap. V annexe I ALCP), car il ne disposait pas des moyens financiers suffisants pour assurer sa subsistance, au sens de l'art. 24 par. 1 al. 1 lettres a et b annexe I ALCP. A raison, l'intéressé ne remet pas en cause ce point de l'arrêt attaqué: au bénéfice de l'aide sociale et à la recherche d'un emploi, il ne réalise manifestement pas cette condition.
2.2 Par ailleurs, le recourant ne saurait, comme il le demande, être assimilé à un travailleur salarié, à défaut «d'occuper un emploi», au sens de l'art. 6 par. 1 et 2 annexe I ALCP ou, du moins, de produire une offre d'embauche de la part d'un employeur (sur la notion autonome de «travailleur» en droit communautaire, cf. Winfried Brechmann, in: Kommentar zu EU-Vertrag und EG-Vertrag, Calliess/Ruffert [éd.], 2ème éd. 2002, ch. 9 ss ad Art. 39 EG-Vertrag; Schneider/Wunderlich, in: Jürgen Schwarze, EU-Kommentar, Baden-Baden 2000, ch. 10 ss ad Art. 39 EGV; Marcel Dietrich, Die Freizügigkeit der Arbeitnehmer in der Europäischen Union, unter Berücksichtigung des schweizerischen Ausländerrechts, Zurich 1995, p. 271 ss et les références citées).
3. 3.1 Il reste à examiner si, en vertu de l'art. 2 par. 1 al. 2 annexe I ALCP, le recourant peut obtenir une autorisation de séjour en sa qualité de ressortissant communautaire à la recherche d'un emploi.
Les premiers juges lui ont dénié ce droit. En se fondant sur le ch. 6.2.5.3 des «Directives et commentaires concernant l'introduction progressive de la libre circulation des personnes» édictées par l'Office fédéral de l'immigration, de l'intégration et de l'émigration (ci-après: «Directives OLCP»), ils ont estimé que les ressortissants communautaires dépourvus, à l'image du recourant, des moyens financiers suffisants pour subvenir à leurs besoins, pouvaient être renvoyés. Bien qu'elle ne soit prévue de manière explicite que pour les «personnes n'exerçant pas une activité économique» (cf. supra consid. 2.1), cette conséquence découle de l'art. 2 par. 1 al. 2 in fine annexe I ALCP: en prévoyant que «les chercheurs d'emploi (...) peuvent être exclus de l'aide sociale pendant la durée (de leur) séjour», cette disposition implique en effet que ceux qui sont sans ressources ne sont pas autorisés à séjourner en Suisse, à moins que l'aide sociale leur soit accordée. Cette interprétation correspond à la jurisprudence rendue en la matière par la Cour de justice des Communautés européennes (cf. arrêt du 26 février 1991, Antonissen, C-292/1989, Rec. 1991 I-745, ch. 1 du résumé et pt 17) ainsi qu'aux avis exprimés par la doctrine (cf. Marcel Dietrich, op. cit., p. 291 s.; Wölker/Grill, in: Kommentar zum Vertrag über die Europäische Union und zur Gründung der Europäischen Gemeinschaft, vol. 1, 6ème éd., 2003, ch. 51 ad Art. 39 EG; Spescha/Sträuli, Ausländerrecht, Zurich 2001, p. 330 ad art. 24 par. 3 annexe I ALCP). Pour les ressortissants communautaires à la recherche d'un emploi, le droit à l'égalité de traitement avec les citoyens suisses se limite donc au «droit de recevoir la même assistance que celle que les bureaux d'emploi de cet Etat (soit la Suisse) accordent à ses propres ressortissants» (cf. art. 2 par. 1 al. 2, deuxième phrase, annexe I ALCP), à l'exclusion du droit, prévu à l'art. 9 par. 2 annexe I ALCP, de bénéficier «des mêmes avantages fiscaux et sociaux que les travailleurs nationaux» (cf. arrêt de la CJCE du 18 juin 1987, Lebon, aff. 316/1985, Rec. 1987 p. 2811, pts 26 et 27; Winfried Brechmann, op. cit., ch. 57 ad Art. 39 EG-Vertrag). Les cantons demeurent cependant libres d'accorder le bénéfice de l'aide sociale aux ressortissants communautaires à la recherche d'un emploi et, le cas échéant, de leur délivrer l'autorisation de séjour prévue à cet effet (cf. Spescha/Sträuli, loc. cit.).
La situation du cas d'espèce est particulière, puisque le recourant a été mis au bénéfice de l'aide sociale et qu'il a pu rester en Suisse jusqu'à aujourd'hui, alors même qu'une autorisation de séjour lui avait pourtant été refusée. Cette - apparente - contradiction s'explique toutefois par le fait que ces questions relèvent de la compétence de différentes autorités qui ne sont pas tenues de coordonner leur action. En tout état de cause, le recourant ne saurait déduire un droit à une autorisation de séjour de l'aide sociale qui lui a été accordée à titre gracieux.
3.2 Le recourant impute l'échec de ses efforts pour trouver un emploi au fait qu'il se serait «heurté à une fin de non-recevoir à chaque fois qu'il sollicitait la possibilité de prendre un emploi.» Son objection est fallacieuse, car elle laisse entendre que les autorités lui auraient mis les bâtons dans les roues pour l'empêcher de trouver un emploi. Or, elles ne lui ont signifié une interdiction de travailler qu'à une seule reprise, pour un motif d'ordre public et à une époque où, l'Accord sur la libre circulation des personnes n'étant pas encore entré en vigueur, elles n'avaient aucune obligation de répondre favorablement à sa demande (cf. arrêt du Tribunal administratif, du 15 mai 2002, rendu dans le cadre de la précédente demande d'autorisation de séjour mentionnée supra dans l'état de fait). Par la suite, si ses démarches sont restées infructueuses, c'est uniquement en raison des refus qu'il a essuyés de la part des employeurs auprès desquels il a postulé (cf. lettres du Service de la population, du 18 février 2003, et de Losinger Construction SA, du 5 mai 2003).
3.3 Quant au grief selon lequel les refus en question procéderaient du fait que l'intéressé n'était - et n'est toujours - pas en possession d'un permis de séjour, il est infondé. En effet, on peine à imaginer que, comme le suggère le recourant, les employeurs suisses ignoreraient les droits que confère aux ressortissants communautaires l'Accord sur la libre circulation des personnes. Au demeurant, à supposer que cet obstacle soit réel, l'Accord permet précisément d'y pallier, en accordant à ceux qui recherchent un emploi un droit de «séjourner pendant un délai raisonnable qui peut être de six mois (et) qui leur permette de prendre connaissance des offres d'emplois correspondant à leurs qualifications professionnelles et de prendre, le cas échéant, les mesures nécessaires aux fins d'être engagés» (art. 2 par. 2 première phrase annexe I ALCP). A l'art. 18 de l'ordonnance du 22 mai 2002 sur l'introduction de la libre circulation des personnes (OLCP; RS 142.203), le Conseil fédéral a concrétisé cette clause de la manière suivante:
"1 Les ressortissants de la CE et de l'AELE n'ont pas besoin d'autorisation s'ils séjournent en Suisse moins de trois mois pour y chercher un emploi.
2 Si la recherche d'un emploi prend plus de trois mois, ils obtiennent une autorisation de séjour de courte durée CE/AELE d'une durée de validité de trois mois par année civile.
3 Cette autorisation peut être prolongée jusqu'à une année au plus pour autant qu'ils soient en mesure de prouver les efforts déployés à cet effet et qu'il existe une réelle perspective d'engagement."
Cette réglementation, en particulier la possibilité de prolonger le séjour au-delà de la période de six mois, qui constitue en principe un «délai raisonnable» pour trouver un emploi, n'est qu'une formalisation de la jurisprudence communautaire (cf. arrêt précité de la CJCE Antonissen du 26 février 1991, pt 21).
En l'espèce, lorsque l'arrêt attaqué a été rendu, le 24 octobre 2003, le recourant séjournait en Suisse depuis plus de deux ans. Au moment déterminant pour apprécier sa situation juridique, il avait dès lors largement dépassé le «délai raisonnable» qui lui revenait. Au surplus, il n'a apporté aucun élément tangible permettant de se convaincre qu'il a fourni des réels efforts pour trouver un emploi ou qu'il était sur le point d'être engagé.
3.4 Pour toutes ces raisons, le recourant ne saurait prétendre l'octroi d'une autorisation de séjour (de courte durée) pour chercheur d'emploi.
4. Il suit de ce qui précède que le recours est mal fondé.
Succombant, le recourant doit, en principe, supporter les frais judiciaires (art. 156 al. 1 OJ). Toutefois, dans la mesure où son recours n'apparaissait pas d'emblée mal fondé et où son état de dénuement est établi, le recourant, qui a demandé l'assistance judiciaire partielle, sera exonéré du paiement de ces frais. Il n'a pas droit à des dépens (art. 159 al. 1 OJ)

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire partielle est admise et le recourant est dispensé des frais de justice.
3. Le présent arrêt est communiqué en copie au mandataire du recourant, au Service de la population et au Tribunal administratif du canton de Vaud, ainsi qu'à l'Office fédéral de l'immigration, de l'intégration et de l'émigration.
Lausanne, le 7 juin 2004
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le président: Le greffier: