Faits: A. Par jugement du 11 décembre 2008, le Juge I du district de Conthey a condamné X._, pour acte d'ordre sexuel avec des enfants et conduite sans permis de conduire, à une peine privative de liberté de 12 mois, avec sursis pendant 2 ans, peine partiellement complémentaire à une peine de 30 jours d'emprisonnement avec sursis pendant 3 ans et à une amende de 700 fr. prononcée le 11 mars 2005 et à une peine de 2 mois d'emprisonnement avec sursis pendant 4 ans et une amende de 1'000 fr. prononcée le 24 novembre 2006. Ce jugement a été confirmé sur appel par le Juge de la Cour pénale II du Tribunal cantonal valaisan, qui a cependant réduit la peine privative de liberté de 12 à 8 mois. B. Cette condamnation repose, en bref, sur les éléments suivants. B.a A la fin du mois de septembre 2004, Y._, née en 1989, a passé quelques jours de vacances dans la famille d'une amie de son âge. Les deux jeunes filles se sont intéressées à un jeune homme blond travaillant sur un chantier non loin de leur lieu de vacances. Par jeu, elles ont discrètement posé un billet dans le véhicule de l'entreprise de construction en demandant à l'inconnu de prendre contact par SMS avec Y._. Lors des échanges SMS, celle-ci a indiqué qu'elle avait 16 ans et son interlocuteur a répondu qu'il en avait 24. Le jour des faits, cachée derrière un arbre sur le chantier, Y._ a envoyé un SMS et s'est aperçue que son interlocuteur n'était pas le jeune homme blond, mais X._. Alors que son amie voulait interrompre le jeu, Y._ s'est dirigée vers l'intéressé, qui l'a invitée à le suivre dans les sous-sols de la construction. Après avoir discuté de tout et de rien, X._ l'a embrassée et s'est rendu compte qu'elle était inexpérimentée. Il n'a pas questionné l'adolescente sur son âge. Il l'a déshabillée et caressée sur tout le corps. Il s'est dévêtu et a exhibé son pénis, s'est masturbé et s'est fait faire une fellation. Il lui a indiqué comment procéder. Il a eu envie de la pénétrer, lui a demandé si elle était vierge, lui a caressé les seins, lui a touché le clitoris avec le pénis et lui a demandé de se détendre, car il avait constaté que la jeune fille était crispée. Il s'est rendu compte que c'était la première relation sexuelle complète qu'entretenait l'adolescente, l'a pénétrée sans protection, après avoir constaté qu'elle avait ses règles, et a éjaculé en elle et sur son sexe. X._ s'est ensuite excusé auprès de Y._ et l'a embrassée. B.b X._ a toujours prétendu que la jeune fille était consentante, ce que cette dernière a nié de façon constante. Elle a expliqué avoir été saisie d'effroi, ne sachant ce qui allait arriver si elle résistait et avoir protesté verbalement au fur et à mesure que son partenaire devenait plus pressant, ne voyant pas la possibilité d'y échapper physiquement. Lors de l'acte sexuel, la jeune fille a affirmé avoir dit « non » et manifesté sa douleur. Elle a subi un examen gynécologique le soir même. C. X._ forme un recours en matière pénale concluant à son acquittement du chef d'accusation d'acte d'ordre sexuel avec des enfants et au renvoi du dossier pour nouvelle décision. Il invoque une violation du principe "in dubio pro reo" et de l'art. 187 ch. 4 CP.