Faits: Faits: A. P._, né en 1963, ressortissant brésilien, est arrivé en Suisse pour la première fois en octobre 1983 et y vit sans interruption depuis octobre 1995. Actuellement, il est étudiant et travaille à mi-temps dans une galerie d'art. Souffrant des séquelles d'un pied adductus droit depuis l'enfance, P._ a déposé, le 16 novembre 2001, une demande de prestations de l'assurance-invalidité pour adultes tendant à la prise en charge de chaussures orthopédiques à titre de moyens auxiliaires. Par décision du 12 mars 2002, l'office cantonal genevois de l'assurance-invalidité (ci-après: l'OCAI) a rejeté la demande, motif pris que le requérant aurait nécessité de tels moyens auxiliaires dès la petite enfance et qu'il n'était dès lors pas assuré à l'assurance-invalidité suisse au moment où le besoin de moyens auxiliaires s'était fait sentir pour la première fois, puisqu'il était arrivé en Suisse à l'âge de 20 ans. Par décision du 12 mars 2002, l'office cantonal genevois de l'assurance-invalidité (ci-après: l'OCAI) a rejeté la demande, motif pris que le requérant aurait nécessité de tels moyens auxiliaires dès la petite enfance et qu'il n'était dès lors pas assuré à l'assurance-invalidité suisse au moment où le besoin de moyens auxiliaires s'était fait sentir pour la première fois, puisqu'il était arrivé en Suisse à l'âge de 20 ans. B. Saisi d'un recours contre cette décision, le Tribunal cantonal genevois des assurances sociales a pris des renseignements auprès du docteur W._, spécialiste en chirurgie orthopédique, qui avait soigné P._ du 30 août 2001 au 11 janvier 2002. Par jugement du 21 avril 2004, le tribunal a admis le recours du prénommé et octroyé les moyens auxiliaires requis. Par jugement du 21 avril 2004, le tribunal a admis le recours du prénommé et octroyé les moyens auxiliaires requis. C. L'OCAI interjette recours de droit administratif contre ce jugement, en concluant à son annulation et à la confirmation de sa décision. P._ n'a pas pris position. L'Office fédéral des assurances sociales a également renoncé à se déterminer. Les juges cantonaux ont déposé des observations. 