Faits:
A. Par jugement du 22 janvier 2008, le juge du district d'Entremont a condamné X._, pour lésions corporelles simples contre son conjoint, menaces contre son conjoint, vols au préjudice d'un familier, dommages à la propriété, violation de domicile, tentative de mêler un enfant à un acte d'ordre sexuel, contrainte sexuelle, exhibitionnisme et voies de fait, à une peine privative de liberté de 510 jours, sous déduction de la détention préventive, à une peine pécuniaire de 10 jours-amende à 20 fr. chacun et à une amende de 200 fr. Il l'a également astreint à un traitement ambulatoire.
B. Par jugement du 18 mai 2009, la Cour pénale II du Tribunal cantonal valaisan a partiellement admis l'appel de X._ en ce sens qu'elle l'a condamné, pour lésions corporelles simples contre son conjoint, menaces contre son conjoint, vol au préjudice d'un familier, dommages à la propriété, violation de domicile, tentative de mêler un enfant à un acte d'ordre sexuel et exhibitionnisme, à une peine privative de liberté de 210 jours et à une peine pécuniaire de 20 jours-amende à 20 fr. chacun, sous déduction de la détention préventive, ainsi qu'à une amende de 200 fr. Elle a confirmé l'astreinte au traitement ambulatoire.
La condamnation pour tentative de mêler un enfant à un acte d'ordre sexuel et exhibitionnisme repose en particulier sur les faits suivants.
B.a Le 13 juin 2006, vers 12 heures 45, Y._ se promenait à vélo avec son fils de quatre ans et demi, à Martigny, sur le chemin des Follatères, le long de la Dranse. A deux reprises, un automobiliste s'est approché d'eux par l'arrière, puis s'est arrêté sans sortir de sa voiture. Alors que les promeneurs faisaient une petite pause, l'automobiliste a stationné son véhicule à une centaine de mètres, en est sorti et est monté sur la berge de la rivière. Lorsqu'elle a repris le chemin avec son enfant, Y._ a vu que l'automobiliste avait son pantalon ouvert et son sexe dehors. Elle a d'abord pensé qu'il urinait avant de constater qu'il se masturbait face à eux. Elle a clairement vu ses mouvements masturbatoires. Elle a pressé l'allure et tenté de cacher l'individu au regard de son fils. Après l'avoir dépassé, elle s'est retournée et a observé que l'homme s'était déplacé de façon à ce qu'elle vît toujours son sexe.
B.b Y._ a appelé son mari qui a contacté la police. Au cours de la ronde effectuée aux alentours, en compagnie des agents, elle a formellement identifié X._. Ce dernier a contesté s'être masturbé et a affirmé avoir quitté son véhicule pour monter au bord de la rivière dans l'intention de « pisser ».
C. Invoquant l'arbitraire et une violation des art. 187 et 194 CP, X._ conclut à son acquittement des accusations de tentative de mêler un enfant à un acte d'ordre sexuel et d'exhibitionnisme. Il requiert également l'assistance judiciaire.

Considérant en droit:
1. Le recourant se plaint d'arbitraire dans l'établissement des faits et l'appréciation des preuves.
1.1 Lorsqu'il vérifie l'application du droit, le Tribunal fédéral se fonde sur les faits établis par l'autorité précédente (<ref-law>). Le recourant ne peut critiquer les faits que s'ils ont été constatés de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.3) - ou en violation du droit au sens de l'<ref-law>, et pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>). Celui qui entend invoquer que les faits ont été établis de manière arbitraire au sens de l'art. 9 Cst. doit, sous peine d'irrecevabilité, le démontrer par une argumentation précise conforme aux exigences de motivation accrues posées à l'<ref-law>. Il ne peut se contenter de critiquer les faits comme il le ferait devant une juridiction d'appel jouissant d'un plein pouvoir d'examen.
En matière d'appréciation des preuves et de constatation des faits, il y a arbitraire lorsque l'autorité ne prend pas en compte, sans aucune raison sérieuse, un moyen de preuve propre à modifier la décision attaquée, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 7.1 p. 398; <ref-ruling> consid. 2.1 p. 9).
1.2 Le recourant soutient que les faits retenus par la Cour pénale (cf. supra consid. B.a) sont contredits par les déclarations de Y._.
Lors de son audition par la police du 13 juin 2006, la plaignante a notamment déclaré ce qui suit (cf. pièce n° 278 du dossier): « Le conducteur a stoppé sa machine au bord de la route, à côté de la Dranse, et est sorti de son véhicule. Je précise que mon fils et moi étions en train de faire une petite pause. On se trouvait à environ 100 mètres de lui. J'ai soudain constaté qu'il avait son pantalon ouvert et son sexe dehors. Au fur et à mesure que mon fils et moi avancions, il restait comme ça sur les berges de la Dranse. Puis, il a commencé à se masturber. Je l'ai clairement vu. Il faisait des mouvements avec son sexe. Je pense que cela a duré bien dix minutes. J'ai accéléré le pas afin de protéger mon fils...Une fois la personne dépassée, je me suis retournée et j'ai vu qu'il s'était déplacé de façon à ce que je voie toujours son sexe ».
A la lecture de ces déclarations, on ne discerne aucune contradiction entre la version de la plaignante et celle finalement retenue par l'autorité cantonale telle qu'exposée ci-dessus au consid. B.a et selon laquelle le recourant se masturbait alors que les promeneurs cheminaient dans sa direction. Le grief est donc rejeté.
1.3 Le recourant explique qu'au vu des circonstances et plus particulièrement de la distance le séparant des promeneurs et de la présence des arbres, il était impossible que Y._ eut pu apercevoir son sexe. Il conteste également s'être positionné sur une éminence dégagée à la vue de tous.
Certes, selon les faits retenus, le recourant a stationné sa voiture à une centaine de mètres des promeneurs, en est sorti et est monté sur la berge de la rivière. Reste que l'acte a duré un certain laps de temps, durant lequel les promeneurs avançaient dans la direction du recourant, avant de le croiser, de sorte que la distance indiquée s'est progressivement réduite, ce qui rendait le comportement incriminé encore plus visible. Par ailleurs, au vu des photos des berges figurant au dossier, la configuration des lieux ne permet en aucun cas d'infirmer la version de la plaignante, qui a affirmé avoir clairement vu les mouvements du recourant sur son sexe et qui, au demeurant, n'avait aucun motif autre que celui de dénoncer un comportement qu'elle appréhendait comme interdit, ce que le recourant ne conteste pas. Enfin, la plaignante a précisé la situation de l'intéressé sur les lieux, celui-ci étant monté sur les berges de la rivière, ce que l'accusé a d'ailleurs lui-même confirmé lors de son audition du 13 juin 2006 (cf. pièce n° 275 du dossier). La critique est donc vaine.
1.4 Le recourant nie avoir voulu être vu par des personnes pouvant potentiellement se trouver à proximité de lui.
Dans une argumentation purement appellatoire, le recourant se contente de nier les faits retenus, à savoir qu'il a cherché à être vu, ce qui est insuffisant pour démontrer l'arbitraire. Par ailleurs, au regard des éléments exposés dans le jugement querellé, et plus précisément de l'attitude de l'intéressé, des circonstances dans lesquelles il s'est masturbé, soit debout sur une éminence dégagée, à la vue de tous, et de sa conscience de la présence des deux promeneurs qu'il avait tout d'abord suivi en voiture, les juges cantonaux pouvaient, sans arbitraire, admettre que le recourant a sciemment cherché à être vu et à mêler l'enfant à un acte d'ordre sexuel. Partant, le grief est infondé.
2. Se plaignant d'une violation de l'<ref-law>, le recourant conteste sa condamnation pour tentative de mêler un enfant à un acte d'ordre sexuel.
2.1 Aux termes de l'<ref-law>, celui qui aura mêlé un enfant de moins de 16 ans à un acte d'ordre sexuel sera puni d'une peine privative de liberté de cinq ans au plus ou d'une peine pécuniaire.
Cette infraction suppose que l'auteur rende l'enfant spectateur d'un acte d'ordre sexuel accompli par lui-même ou un tiers. Il ne suffit pas que le jeune soit le témoin fortuit de l'acte. Il doit être utilisé comme un élément du jeu sexuel. Tel est le cas lorsque l'auteur se masturbe devant un enfant. Il importe peu que ce dernier ait saisi ou non le caractère sexuel de l'acte et le but poursuivi par l'auteur. Il doit toutefois percevoir directement l'acte par ses sens, en être le spectateur ou l'auditeur (cf. FF 1985 II 1082; <ref-ruling> consid. 3.1).
D'un point de vue subjectif, l'auteur commet sciemment l'acte d'ordre sexuel devant l'enfant et veut que celui-ci le perçoive. Le dol éventuel ne suffit pas. Ainsi, celui qui admet que l'enfant peut percevoir l'acte d'ordre sexuel et qui accepte de courir ce risque, n'est pas punissable (ATF 6S.241/2002 du 20 septembre 2002, in Praxis 2003 n° 114 p. 610 consid. 1.2). Déterminer ce que l'auteur d'une infraction a su, cru, voulu ou accepté relève de l'établissement des faits (<ref-ruling> consid. 3c p. 252).
2.2 Le recourant conteste avoir voulu utiliser l'enfant de Y._ comme un élément de son prétendu jeu sexuel et la réalisation de l'aspect subjectif de l'infraction.
Selon les constatations cantonales au sujet desquelles aucun arbitraire n'a été démontré, le recourant avait conscience de la présence des deux promeneurs et, au vu de son attitude et des circonstances (cf. supra consid. B.a et 1.4), a sciemment cherché à être vu des passants et à mêler l'enfant à un acte d'ordre sexuel. Sur la base de ces éléments, la Cour pénale n'a pas violé le droit fédéral en admettant la réalisation des conditions de l'infraction de tentative de mêler un enfant à un acte d'ordre sexuel.
3. Invoquant une violation de l'<ref-law>, le recourant conteste sa condamnation pour exhibitionnisme.
3.1 Selon cette disposition, celui qui se sera exhibé sera, sur plainte, puni d'une peine pécuniaire de 180 jours-amende au plus.
Cette norme sanctionne le fait de montrer ses organes sexuels ou, pour un homme, de dénuder son membre, à des fins d'excitation ou de de satisfaction sexuelle. Elle suppose que la victime voie effectivement le sexe nu (ATF 6S.556/2006 du 27 mars 2007 consid. 3.2).
D'un point de vue subjectif, la personne qui s'exhibe doit le faire intentionnellement. L'auteur doit ainsi vouloir que la victime le voie. Le dol éventuel ne suffit pas (cf. K. MENG/M. SCHWAIBOLD, Basler Kommentar, Strafrecht II, 2ème éd., art. 194 n° 23 p. 1173; S. TRECHSEL ET AL., Schweizerisches Strafgesetzbuch, Praxiskommentar, art. 194 n° 3 p. 937; J. REHBERG/N. SCHMID/A. DONATSCH, Strafrecht III, Delikte gegen den Einzelnen, 8ème éd, p. 442; contra: B. CORBOZ, Les infractions en droit suisse, vol. I, Berne 2002, art. 194 n° 9 p. 779).
3.2 Le recourant conteste avoir aperçu les promeneurs et avoir voulu être observé dans sa prétendue exhibition.
Selon les constatations cantonales, le recourant a dénudé son sexe et s'est masturbé au bord d'un chemin fréquenté. Il n'a pas cessé son activité à l'approche d'une femme et d'un enfant, se tournant même dans leur direction afin d'être vu. Y._ a perçu ce que faisait l'intéressé. Etant donné les circonstances dans lesquelles celui-ci s'est masturbé et sa conscience de la présence des promeneurs, il a cherché à être vu de ces derniers. Au regard de ces éléments au sujet desquels aucun arbitraire n'est démontré conformément aux exigences légales (cf. supra consid. 1.1), la Cour pénale n'a pas violé le droit fédéral en admettant la réalisation de l'infraction d'exhibitionnisme visée par l'<ref-law>.
4. Sur le vu de ce qui précède, le recours est rejeté dans la mesure où il est recevable. Comme ses conclusions étaient dénuées de chance de succès, le recourant doit être débouté de sa demande d'assistance judiciaire (<ref-law> a contrario) et supporter les frais de justice (<ref-law>). Ceux-ci seront réduits pour tenir compte de la situation financière de l'intéressé.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 1'600 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Cour pénale II.
Lausanne, le 3 septembre 2009
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Juge présidant: La Greffière:
Schneider Bendani