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. 