Faits: A. A.a Ressortissant français, F._ a exercé l'activité de serveur à Y._ comme travailleur frontalier jusqu'au 24 août 1990. Le lendemain, présentant un état comateux prolongé à la suite d'une injection d'héroïne, il a dû être hospitalisé d'urgence à l'Hôpital X._, où les diagnostics de syndrome des loges de l'avant-bras droit et de la jambe droite avec atteinte du nerf sciatique poplité interne et externe et de toxicomanie ont été posés. En incapacité de travail totale depuis lors, F._ a été mis au bénéfice d'une rente entière d'invalidité, fondée sur un degré d'invalidité de 100 %, à partir du 1er août 1991 (décision du 25 septembre 1992). Par courrier du 4 septembre 1997, l'intéressé a demandé à l'Office cantonal genevois de l'assurance-invalidité (ci-après: l'OCAI) à être mis au bénéfice d'une mesure de réadaptation professionnelle dans le secteur de la vente ou comme chauffeur-livreur. L'administration n'a jamais répondu à cette demande. A.b Procédant à une révision d'office de la rente, l'OCAI a soumis F._ à une expertise de la Clinique Z._. Les docteurs P._ et M._ ont indiqué que celui-ci présentait, notamment, une personnalité émotionnellement labile de type impulsif et des séquelles d'un syndrome des loges des membres supérieurs et inférieurs droits avec une neuropathie sensitivo-motrice, radiale, ulnaire, péronière et tibiale à droite. Ils ont conclu qu'il était en mesure, au moment où a été rendu le rapport d'expertise le 31 octobre 2001, d'exercer une activité légère tenant compte des limitations neurologiques, à savoir n'impliquant pas l'usage de la force, ni de déplacements fréquents et de longue durée. Selon eux, comme l'intéressé avait signalé une amélioration en 1997 et avait exprimé la volonté de reprendre une activité à temps partiel (cf. questionnaire pour la révision de la rente du 19 octobre 1999), la situation semblait stabilisée depuis ce moment. Fort de ces conclusions, l'Office AI pour les assurés résidant à l'étranger (ci-après: l'office AI) a rendu une décision, le 17 juillet 2002, par laquelle il a remplacé la rente entière d'invalidité par une demi- rente dès le 1er septembre 2002. B. B.a A la suite d'un recours de F._ qui concluait au maintien de sa rente entière ou à l'octroi de mesures de réadaptation professionnelle, 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) l'a admis et renvoyé la cause à l'administration pour instruction médicale complémentaire sur le plan psychique (jugement du 16 mai 2003). Chargé de ce fait d'une expertise, le docteur A._, psychiatre et psychothérapeute, a confirmé les conclusions de ses confrères de la Clinique Z._ et conclu à une capacité de travail de 50 % «comme établie» par ceux-ci (rapport du 15 décembre 2003). Se fondant sur ces conclusions, l'office AI a, par décision du 12 février 2004, remplacé la rente entière d'invalidité par une demi-rente dès le 1er septembre 2002, au motif que l'intéressé subissait une perte de gain de 56 %. Cette décision est entrée en force. B.b Interpellé par F._ qui lui rappelait avoir requis des mesures de réadaptation professionnelle, l'office AI a, le 23 juin 2004, rejeté sa demande. Il a considéré qu'au moment où l'état de santé du requérant s'était amélioré, en 1997, celui-ci n'avait pas la qualité d'assuré. Sur opposition de F._, l'administration a confirmé ce refus dans une décision sur opposition du 23 novembre 2004. L'intéressé a déféré cette décision à la Commission qui l'a débouté par jugement du 27 mai 2005. Elle a considéré, en substance, que le cas d'assurance s'était réalisé en 1997 déjà, mais en tout cas avant le 1er juin 2002. A ce moment-là, F._ ne remplissait pas les conditions d'assurance au regard de l'art. 11 de la Convention franco-suisse de sécurité sociale, de sorte que son droit au reclassement devait être nié. C. F._ interjette un recours de droit administratif contre ce jugement dont il demande la réforme, en ce sens que lui soit reconnu le droit à une mesure de reclassement au sens de l'art. 17 LAI. Il conclut par ailleurs au renvoi du dossier à l'office AI pour détermination du genre et de l'étendue de la mesure. L'office AI et l'OCAI concluent au rejet du recours. De même, l'Office fédéral des assurances sociales (Secteur Conventions internationales), sur les déterminations duquel F._ s'est exprimé le 7 décembre 2005, préavise pour le rejet du recours. 