Faits:
A. Le 28 avril 2003, S._, né le 15 janvier 1937, ressortissant français et domicilié en France, a présenté une demande de rente de vieillesse, en indiquant avoir travaillé quatre ans (de mars 1953 à mars 1957) en Suisse.
Par décision du 13 juin 2003, confirmée sur opposition du requérant le 31 juillet suivant, la Caisse suisse de compensation (ci-après: la caisse) a rejeté la demande, au motif qu'il n'avait cotisé à l'AVS que durant six mois au total.
B. S._ a recouru devant la Commission fédérale de recours en matière d'AVS/AI pour les personnes résidant à l'étranger (ci-après: la commission) qui l'a débouté par jugement du 2 octobre 2003.
C. S._ interjette recours de droit administratif contre ce jugement dont il requiert implicitement l'annulation. Il demande que son dossier soit revu faisant valoir qu'il avait travaillé en Suisse pendant au moins trois ans.
La caisse conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales (OFAS) a renoncé à se déterminer.

Considérant en droit:
1. Le litige porte sur le droit du recourant à une rente ordinaire de l'AVS, singulièrement sur la durée de cotisations ouvrant un tel droit.
2. 2.1 Dès lors que le recourant, de nationalité française et domicilié en France, fait valoir un droit à une rente de vieillesse suisse en raison de son activité lucrative exercée en Suisse dans les années cinquante, il convient d'examiner dans quelle mesure 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 (Accord sur la libre circulation des personnes; ALCP; RS 0.142.112.681) s'applique au présent cas. L'ALCP est entré en vigueur le 1er juin 2002, soit après l'accomplissement par le recourant de l'âge ouvrant le droit à une rente de vieillesse suisse (le 15 janvier 2002; <ref-law>), mais avant que la décision litigieuse n'ait été rendue (le 31 juillet 2003).
Le cas échéant, le recourant serait soumis à l'ALCP et aux règlements auxquels il renvoie du point de vue personnel - ressortissant d'un Etat membre, S._ doit être considéré comme un travailleur qui est ou a été soumis à la législation d'un ou de plusieurs Etats membres (art. 2 par. 1 du règlement n° 1408/71) - et du point de vue matériel - le règlement n° 1408/71 s'appliquant à toutes les législations relatives aux branches de sécurité sociale qui concernent les prestations de vieillesse (art. 4 par. 1 let. c dudit règlement).
2.2 Selon l'art. 1 par. 1 de l'Annexe II «Coordination des systèmes de sécurité sociale» de l'accord, fondée sur l'art. 8 de l'accord et faisant partie intégrante de celui-ci (art. 15 de l'accord), en relation avec la section A de cette annexe, les Parties contractantes appliquent entre elles en particulier le Règlement (CEE) no 1408/71 du Conseil du 14 juin 1971 relatif à l'application des régimes de sécurité sociale aux travailleurs salariés, aux travailleurs non salariés et aux membres de leur famille qui se déplacent à l'intérieur de la Communauté (règlement n° 1408/71), ainsi que le Règlement (CEE) no 574/72 du Conseil du 21 mars 1972 fixant les modalités d'application des régimes de sécurité sociale aux travailleurs salariés, aux travailleurs non salariés et aux membres de leur famille qui se déplacent à l'intérieur de la Communauté (règlement n° 574/72), ou des règles équivalentes. L'<ref-law>, entré en vigueur le 1er juin 2002, renvoie à ces deux règlements de coordination.
2.3 Les dispositions transitoires pour les travailleurs salariés, prévues à l'art. 94 du règlement n° 1408/71, posent le principe selon lequel ledit règlement ne crée aucun droit à la rente pour une période antérieure à sa mise en application dans l'Etat concerné (art. 94 par. 1; voir <ref-ruling> consid. 1b/aa). Elles ne résolvent pas la question de savoir si une prétention née en raison d'un événement survenu avant l'entrée en vigueur de ce règlement dans l'Etat intéressé, mais sur laquelle l'administration ne s'est prononcée qu'après ce moment, est réglée selon le droit communautaire, respectivement conventionnel, ou si doivent être appliquées les normes en vigueur jusqu'à cette date (arrêt E. du 12 mars 2004, H 14/03, prévu pour la publication, consid. 4.2.1 et les références).
En revanche, selon l'art. 118 par. 1 du règlement n° 574/72, «lorsque la date de la réalisation du risque se situe (...) avant la date de mise en application du règlement d'application sur le territoire de l'Etat membre intéressé et que la demande de pension ou de rente n'a pas encore donné lieu à liquidation avant cette date, cette demande entraîne, pour autant que des prestations doivent être accordées au titre en question, pour une période antérieure à cette dernière date, une double liquidation:
- a) pour la période antérieure à la date de mise en application du règlement d'application sur le territoire de l'Etat membre intéressé, conformément (...) aux conventions en vigueur entre les Etats membres en question;
- b) pour la période commençant (...) à la date de mise en application du règlement d'application sur le territoire de l'Etat membre intéressé, conformément au règlement.
Toutefois, si le montant calculé en application des dispositions visées au point a) est plus élevé que celui calculé en application des dispositions visées au point b), l'intéressé continue à bénéficier du montant calculé en application des dispositions visées au point a).»
Conformément à cette disposition, il y a lieu d'examiner le droit éventuel du recourant à une rente de vieillesse, d'une part, sous l'angle de la Convention de sécurité sociale entre la Confédération suisse et la République française, du 3 juillet 1975 (RS 0.831.109.349.1; ci-après: la convention franco-suisse; suspendue depuis le 1er juin 2002 conformément à l'<ref-law>; [voir à ce sujet, <ref-ruling> consid. 2.2 et l'arrêt S. du 5 février 2004, H 37/03, consid. 6.2, prévu pour la publication]) - pour la période du 1er février (date de la naissance éventuelle du droit à la rente; <ref-law>) au 31 mai 2002, et d'autre part, sous l'angle de l'ALCP pour la période à partir du 1er juin 2002.
3. 3.1 Tant la convention franco-suisse que l'ALCP contiennent des règles relatives à une période d'assurance inférieure à une année.
3.1.1 Selon l'art. 18 al. 2 de la convention franco-suisse, si, pour l'ouverture du droit à une prestation selon la législation de l'un des Etats contractants, une période minimale d'assurance d'une année est exigée, l'institution compétente de cet Etat procède au calcul direct de la prestation en fonction des seules périodes accomplies sous la législation qu'elle applique. Aux termes de l'art. 19 de cette convention, lorsque les périodes d'assurance accomplies sous la législation d'un des Etats sont inférieures à un an, aucune prestation n'est due au titre de la législation de cet Etat. Ces périodes sont néanmoins prises en considération pour l'ouverture des droits par totalisation au regard de la législation de l'autre Etat dans les termes de l'art. 18, à moins qu'il n'en résulte une diminution de la prestation due au titre de la législation de cet Etat (art. 19 al. 2 de la convention franco-suisse).
3.1.2 Selon l'art. 48 par. 1 du règlement n° 1408/71, nonobstant l'art. 46 par. 2 (relatif à la liquidation des prestations lorsqu'il doit être fait application de l'art. 45 dudit règlement [prise en compte des périodes d'assurance ou de résidence accomplies dans un autre Etat membre] pour que soient satisfaites les conditions requises par un Etat membre pour avoir droit aux prestations), l'institution d'un Etat membre n'est pas tenue d'accorder des prestations au titre de périodes accomplies sous la législation qu'elle applique et qui sont à prendre en considération au moment de la réalisation du risque si la durée totale desdites périodes n'atteint pas une année et compte tenu de ces seules périodes, aucun droit aux prestations n'est acquis en vertu de cette législation.
Cette disposition décharge l'institution compétente d'un Etat membre de son obligation de reconnaître le droit à une pension de retraite lorsque la durée des périodes de cotisation accomplies sous la législation de cet Etat est inférieure à un an ou lorsqu'aucune cotisation n'a été versée (arrêt de la Cour de justice des Communautés européennes [CJCE] du 20 février 1997, Martinez Losada e.a., C-88/95, C-102/95 et C-103/95, Rec. p. I-869, point 11; sur le rôle de la jurisprudence de la CJCE pour les tribunaux suisses, cf. <ref-law>). L'art. 48 du règlement n° 1408/71 n'est toutefois pas applicable lorsque le droit aux prestations du travailleur migrant ou de ses survivants dérive déjà des seules dispositions de la législation de l'Etat membre en cause (arrêt de la CJCE du 20 novembre 1975, Borella, 49/75, Rec. p. 1461). Même en cas de période d'assurance ou de résidence inférieure à douze mois, l'institution n'est ainsi libérée de son devoir d'accorder des prestations, que lorsque celle-ci ne suffit pas, conformément à la législation de l'Etat membre concerné, à fonder un droit autonome (c'est-à-dire sans prendre en considération des périodes accomplies dans d'autres Etats membres selon l'art. 45 du règlement n° 1408/71) aux prestations (Rolf Schuler in: Maximilian Fuchs (éd.), Kommentar zum Europäisches Sozialrecht, 3ème éd., Baden-Baden 2002, ad art. 48 p. 382 n° 7).
Conformément à l'art. 48 par. 2 du règlement n° 1408/71, l'institution compétente de chacun des autres Etats membres concernés prend en compte les périodes visées au par. 1, pour l'application de l'art. 46 par. 2, à l'exception du point b). Au cas où l'application du par. 1 aurait pour effet de décharger de leurs obligations toutes les institutions des Etats membres concernés, les prestations sont accordées exclusivement au titre de la législation du dernier de ces Etats dont les conditions se trouvent satisfaites comme si toutes les périodes d'assurance et de résidence accomplies et prises en compte conformément à l'art. 45 par. 1 à 4 avaient été accomplies sous la législation de cet Etat (art. 48 par. 3 du règlement n° 1408/71). Cette disposition a pour but d'éviter qu'une personne qui a exercé son droit de libre circulation, mais n'a pas été assurée une année au moins dans aucun Etat membre ne perde le bénéfice des périodes d'assurance accomplies à l'étranger (Alessandra Prinz, Les effets de l'Accord sur les prestations AVS et AI, in: Les effets des Accords bilatéraux avec l'Union européenne sur les assurances sociales suisses, Sécurité sociale, CHSS 2/2002, p. 81).
3.2 Le jugement entrepris expose de manière exacte les dispositions légales et réglementaires du droit suisse régissant l'octroi d'une rente ordinaire de vieillesse (<ref-law>; <ref-law> dans sa teneur en vigueur jusqu'au 31 décembre 2002 [entrée en vigueur de la loi fédérale sur la partie générale du droit des assurances sociales, LPGA, au 1er janvier 2003] applicable en l'espèce [<ref-ruling> consid. 1, 121 V 366 consid. 1b]), de sorte qu'on peut y renvoyer.
4. Nonobstant les recherches effectuées par l'intimée, aucun versement de cotisations AVS n'a pu être établi au nom du recourant en dehors des cotisations versées en 1956 et 1957 pour l'activité exercée auprès de la boulangerie-pâtisserie Z._ à Bâle, dont la durée est inférieure à une année (cf. extrait du compte individuel). Le recourant ne peut dès lors prétendre une rente de vieillesse que par le biais d'une rectification du compte individuel.
4.1 Aux termes de l'<ref-law>, pour le cas où il n'a pas été demandé d'extrait de compte, la caisse ne peut, lors de la réalisation du risque assuré, créditer un compte individuel d'une inscription de cotisations que si l'inexactitude de l'absence d'une telle inscription est «manifeste» ou «pleinement» prouvée.
En vertu de l'<ref-law>, les revenus de l'activité lucrative obtenus par un salarié et sur lesquels l'employeur a retenu les cotisations légales sont inscrits au compte individuel de l'intéressé, même si l'employeur n'a pas versé les cotisations en question à la caisse de compensation. Cela vaut également lorsque le salarié et l'employeur ont conclu une convention de salaire net, c'est-à-dire lorsque l'employeur prend en charge la totalité des cotisations sociales à sa charge. Il n'y a matière à rectification que si la preuve absolue est rapportée (cf. <ref-ruling> consid. 3d) qu'un employeur a effectivement retenu des cotisations AVS sur les revenus versés ou qu'une convention de salaire net a été fixée entre cet employeur et le salarié; établir l'exercice d'une activité lucrative salariée n'y suffit pas.
4.2 En l'espèce, le recourant a produit plusieurs documents démontrant qu'il a effectué un apprentissage de boulanger-pâtissier auprès de la boulangerie-pâtisserie A._ à Bâle, du 14 février 1953 au 14 août 1955. Si ces pièces sont certes de nature à prouver que le recourant a bel et bien travaillé comme apprenti en Suisse durant plus de deux ans, elles n'établissent toutefois pas que son maître d'apprentissage a retenu des cotisations AVS sur les revenus qu'il allègue avoir obtenus à cette époque. En effet, les attestations produites ne contiennent aucune inscription relative au versement d'un salaire, ni à une déduction du salaire à ce titre. Par ailleurs, le recourant ne prétend pas qu'une convention de salaire net aurait été conclue avec son ancien employeur. Dès lors, les documents versés à la procédure ne sauraient suffire au regard des exigences de preuve posées par l'<ref-law> et la jurisprudence y relative, pour établir l'existence de cotisations AVS durant la période litigieuse, cela d'autant moins que la caisse a procédé aux recherches nécessaires auprès de la caisse de compensation compétente, toutefois sans succès. Pour le surplus, le certificat de travail signé par Z._, relatif à l'activité exercée par le recourant du 12 octobre 1956 au 28 février 1957, se rapporte à une période pour laquelle le versement des cotisations est enregistré sur son compte individuel.
4.3 En conséquence, seule la période de cotisations pendant laquelle le recourant a travaillé auprès de la boulangerie-pâtisserie Z._ est déterminante. Selon la jurisprudence, les périodes de cotisations des années 1946 à 1968 doivent être fixées exclusivement selon les tables AVS/AI pour la détermination de la durée présumable de cotisation des années 1948-1968 publiées à l'appendice IX des Directives concernant les rentes (DR) de l'assurance vieillesse, survivants et invalidité fédérale de l'OFAS (<ref-ruling> consid. 3b; RDAT 1999 II n° 64 p. 239). Au regard des revenus obtenus par le recourant selon l'extrait du compte individuel et de la table 20 (industrie et métiers de l'alimentation) applicables en l'espèce, on constate que celui-ci ne peut se prévaloir que d'une durée de cotisations de quatre mois au total (deux mois en 1956 et deux mois en 1957) - et non pas de six mois comme retenu par l'intimée dans la décision litigieuse. Le recourant ne remplit donc pas la condition minimale d'assurance d'une année prévue par l'<ref-law> en relation avec l'<ref-law>, laquelle doit être nécessairement remplie pour l'ouverture du droit à une rente ordinaire de vieillesse. L'intimée était dès lors en droit, tant en application de l'art. 19 de la convention franco-suisse que de l'art. 48 du règlement n° 1408/71, de refuser toute prestation de l'AVS au recourant. Partant, le jugement entrepris n'est pas critiquable et le recours se révèle mal fondé.
5. Conformément au chiffre 2 du dispositif du jugement entrepris, le dossier devra être retourné à l'intimée pour qu'elle mette en oeuvre la procédure inter-étatique qui permettra aux autres Etats éventuellement concernés de prendre en compte les périodes de cotisations effectuées en Suisse au sens des art. 48 par. 2 et 3 du règlement n° 1408/71 (cf. Circulaire sur la procédure pour la fixation des rentes dans l'AVS/AI [CIBIL], ch. 5004-5006).

Par ces motifs, le Tribunal fédéral des assurances prononce:
1. Le recours est rejeté.
2. Il n'est pas perçu de frais de justice.
3. Le présent arrêt sera communiqué aux parties, à la Commission fédérale de recours en matière d'AVS/AI pour les personnes résidant à l'étranger et à l'Office fédéral des assurances sociales.
Lucerne, le 28 mai 2004
Au nom du Tribunal fédéral des assurances
Le Président de la Ire Chambre: La Greffière: