Sachverhalt: A. Am 11. Juni 2008 sprach das Kantonsgericht Nidwalden X._ der qualifizierten Vergewaltigung sowie der qualifizierten sexuellen Handlung mit einem Kind schuldig und bestrafte ihn mit einer teilbedingten Freiheitsstrafe von 3 Jahren. Davon wurden 18 Monate als vollziehbar erklärt, unter Anrechnung von 122 Tagen Untersuchungshaft. Der Vollzug der übrigen 18 Monate Freiheitsstrafe wurde bei einer Probezeit von 3 Jahren aufgeschoben. Gegen dieses Urteil erhob die Staatsanwaltschaft des Kantons Nidwalden hinsichtlich der Kostenfrage Beschwerde an das Obergericht des Kantons Nidwalden. X._ seinerseits erklärte Appellation. Das Obergericht wies die Appellation mit Urteil vom 23. April 2009 ab und bestätigte in Gutheissung der Kostenbeschwerde das vorinstanzliche Urteil mit Ausnahme der Kostenauflage. B. X._ führt Beschwerde in Strafsachen an das Bundesgericht. Er beantragt, das angefochtene Urteil sei aufzuheben, und die Sache sei zur neuen Beurteilung an das Kantonsgericht Nidwalden, eventualiter an die Vorinstanz zurückzuweisen. Die Rückweisung sei mit der gerichtlichen Auflage zu versehen, dass vorgängig über den Ausstand derjenigen Richter entschieden werde, die beim angefochtenen Entscheid des Kantonsgerichts Nidwalden mitgewirkt hätten. Im Falle eines Entscheids in der Sache selbst sei er von Schuld und Strafe freizusprechen. Eventualiter sei im Falle eines Schuldspruchs die Sanktion auf eine bedingte Freiheitsstrafe von 2 Jahren bei einer Probezeit von 3 Jahren festzusetzen. Ihm sei für das vorliegende Verfahren zudem eine angemessene Parteientschädigung zu entrichten, die unentgeltliche Rechtspflege zu gewähren sowie Armin Durrer, als unentgeltlicher Rechtsvertreter beizugeben. C. Es wurden keine Vernehmlassungen eingeholt.