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.
Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
Die Geschädigte, A._ (geb. 28. April 1989), sowie ihre Kollegin B._ hielten sich an einem Mittwochnachmittag Ende Juni oder Anfang Juli 2004 beim Badeplatz in Stansstad auf. Dort nötigte der Beschwerdeführer, zusammen mit Z._, die Geschädigte gegen ihren Willen gewaltsam zu (geschütztem) Geschlechtsverkehr. Z._ packte dabei ihre Arme, zog diese über den Kopf und kreuzte sie, um sie mit einer Hand auf den Boden pressen zu können. Gleichzeitig kniete er nieder und drückte mit der anderen Hand den Unterkiefer der Geschädigten nach oben. Währenddessen drückte der Beschwerdeführer ihre Beine auseinander, öffnete kniend seine Hose, schob ihr Bikini zur Seite und führte seinen bereits vorgängig durch ein übergezogenes Kondom geschützten Penis zweimal in deren Scheide ein. Anschliessend standen der Beschwerdeführer und Z._ unverzüglich auf und verliessen wortlos den Tatort (erstinstanzliches Urteil, S. 35).
2. 2.1 Der Beschwerdeführer macht eine willkürliche Beweiswürdigung sowie eine Verletzung des Grundsatzes "in dubio pro reo" geltend. Bei objektiver Würdigung des Beweisergebnisses bestünden offensichtlich erhebliche bzw. schlechterdings nicht zu unterdrückende Zweifel an seiner Schuld. Er erwähnt hierbei verschiedene angebliche Diskrepanzen und Widersprüche zwischen den Aussagen der Geschädigten und den einvernommenen Zeugen (Beschwerde, S. 7 ff.).
Es sei willkürlich und unhaltbar, dass die Vorinstanz von der Richtigkeit der Aussagen der Geschädigten ausgehe, obschon diese aufgrund der Aussagen der Zeugen C._, D._ und B._ offensichtlich mit der tatsächlichen Situation im Widerspruch stünden. Die Nichtberücksichtigung widersprechender Aussagen stelle eine willkürliche Beweiswürdigung dar (Beschwerde, S. 10 ff.).
2.2 Die Vorinstanz hält fest, dass in Würdigung der gesamten Aktenlage ohne weiteres auf die Aussagen der Geschädigten abgestellt werden könne. Die vom Beschwerdeführer geltend gemachten Widersprüche erwiesen sich als untauglich oder erklärbar und vermöchten keine Zweifel am Erlebnisbezug des von der Geschädigten geschilderten Sachverhalts zu begründen. Zudem sei auch kein konkretes Interesse der Geschädigten erkennbar, weshalb sie den Beschwerdeführer zu Unrecht einer strafbaren Handlung bezichtigen sollte. Die Aussagen des Beschwerdeführers wiesen demgegenüber weniger innere Geschlossenheit und Folgerichtigkeit sowie offensichtliche Widersprüche auf (angefochtenes Urteil, S. 19).
2.3 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts durch die Vorinstanz kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich im Sinne von Art. 9 BV ist (BGE 133 II 249 E. 1.2.2) oder wenn sie auf einer Verletzung von schweizerischem Recht im Sinne von Art. 95 BGG beruht (Art. 97 Abs. 1 BGG). Die Rüge der offensichtlich unrichtigen Feststellung des Sachverhalts prüft das Bundesgericht gemäss Art. 105 Abs. 2 BGG nur insoweit, als in der Beschwerde explizit vorgebracht und substantiiert dargelegt wird, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (BGE 133 II 249 E. 1.4.3; 130 I 258 E. 1.3 mit Hinweisen).
2.4 Was der Beschwerdeführer gegen die tatsächlichen Feststellungen der Vorinstanz einwendet, erschöpft sich in einer blossen appellatorischen Kritik am angefochtenen Urteil, die für die Begründung einer willkürlichen Feststellung des Sachverhalts nicht genügt. Der Beschwerdeführer beschränkt sich darauf, die eigene Sichtweise der Verhältnisse darzulegen und einzelne angebliche Diskrepanzen im Aussageverhalten der Geschädigten darzustellen. So behauptet er, sie habe ihr Abwehrverhalten anlässlich der Tathandlung, die Art und Weise des Festhaltens durch Z._, sowie die Bekanntheit der Täter widersprüchlich zu den Aussagen ihres Freundes geschildert. Gleiches gelte hinsichtlich des Zeitpunktes, wann sie die Tat ihrem Freund erzählt habe. Zudem habe sie bereits drei Monate nach dem Vorfall mit ihrem Freund wieder Geschlechtsverkehr gehabt (Beschwerde, S. 8 ff.). Weitere Unstimmigkeiten erblickt der Beschwerdeführer bezüglich einer angeblichen telefonischen Drohung der Schwester ihm gegenüber (Beschwerde, S. 12 f.) sowie bei der Frage, ob die Geschädigte das Eincrèmen durch den Beschwerdeführer von Anbeginn oder erst im späteren Verlauf abgelehnt hat (Beschwerde, S. 13 f.).
2.5 Die Ausführungen des Beschwerdeführers sind insgesamt nicht geeignet, offensichtlich erhebliche und schlechterdings nicht zu unterdrückende Zweifel daran darzutun, dass sich der Sachverhalt, wie von der Vorinstanz dargestellt, verwirklicht hat. Er legt auch nicht dar, weshalb die erwähnten Zeugen im Vergleich zur Geschädigten glaubhafter ausgesagt hätten. Für die Begründung von Willkür genügt praxisgemäss nicht, dass das angefochtene Urteil mit der Darstellung des Beschwerdeführers nicht übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre (BGE 131 IV 100 nicht publ. E. 4.1; BGE 127 I 54 E. 2b mit Hinweisen). Willkür im Sinne von Art. 9 BV liegt nach ständiger Rechtsprechung nur vor, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (BGE 134 I 140 E. 5.4). Dies ist vorliegend nicht der Fall. Auf die Beschwerde ist in diesem Punkt nicht einzutreten.
3. 3.1 Der Beschwerdeführer rügt eine Verletzung des Anspruchs auf einen verfassungsmässigen Richter gemäss Art. 30 Abs. 1 BV. Die erste Instanz habe diesen Grundsatz verletzt, indem sie insgesamt 23 Seiten unbesehen und unreflektiert von der Anklageschrift abgeschrieben habe. Entgegen der Auffassung der Vorinstanz beschränkten sich die abgeschriebenen Passagen nicht nur auf die Akten- und Beweislage, sondern umfassten auch den juristischen Bereich. Der Anschein der Befangenheit und die Gefahr der Voreingenommenheit seien mehr als begründet (Beschwerde, S. 6 f.).
3.2 Die Vorinstanz erwähnt, eine richterliche Vorbefassung könne nicht aus dem Umstand abgeleitet werden, dass das Gericht die rechtliche Würdigung der Anklage teilweise zu eigen gemacht habe. Sei das Gericht von deren rechtlichen Würdigung überzeugt, stehe es ihm frei, diesen Ausführungen zu folgen. Eine wortgetreue Abschrift sei nicht zu beanstanden. Zudem habe sich die erste Instanz mit der Argumentation des Beschwerdeführers ausführlich auseinandergesetzt (angefochtenes Urteil, S. 8 f.).
3.3 Nach Art. 30 Abs. 1 BV und Art. 6 Ziff. 1 EMRK hat der Einzelne Anspruch darauf, dass seine Sache von einem unparteiischen, unvoreingenommenen und unbefangenen Richter ohne Einwirken sachfremder Umstände entschieden wird. Ob diese Garantien verletzt sind, prüft das Bundesgericht frei (BGE 133 I 1 E. 5.2; 131 I 31 E. 2.1.2.1 je mit Hinweisen). Voreingenommenheit und Befangenheit werden nach der Rechtsprechung angenommen, wenn Umstände vorliegen, die bei objektiver Betrachtung geeignet sind, Misstrauen in die Unparteilichkeit des Richters zu erwecken. Solche Umstände können entweder in einem bestimmten Verhalten des betreffenden Richters oder in gewissen äusseren Gegebenheiten funktioneller und organisatorischer Natur begründet sein. Bei der Beurteilung solcher Umstände ist nicht auf das subjektive Empfinden einer Partei abzustellen. Das Misstrauen in die Unvoreingenommenheit muss vielmehr in objektiver Weise begründet erscheinen. Es genügt, wenn Umstände vorliegen, die bei objektiver Betrachtung den Anschein der Befangenheit und Voreingenommenheit erwecken. Für die Ablehnung wird nicht verlangt, dass der Richter tatsächlich befangen ist (BGE 134 I 238 E. 2.1. S. 240 mit Hinweisen).
3.4 Eine wörtliche Übernahme von Ausführungen aus der Anklageschrift führt nach richtiger Auffassung der Vorinstanz nicht zu einer Vorbefassung der beteiligten Richter. Dies wäre laut Vorinstanz nur der Fall, wenn diese Richter schon in einem früheren Stadium am Verfahren beteiligt gewesen wären, was der Beschwerdeführer jedoch nicht behauptet und auch nicht ersichtlich ist. Zudem hat sich gemäss Vorinstanz die erste Instanz mit den Argumenten der Verteidigung befasst, weshalb diese auch ihrer Begründungspflicht nachgekommen ist. Diese Ausführungen sind nicht zu beanstanden. Die Beschwerde ist in diesem Punkt unbegründet.
3.5 Der Beschwerdeführer wendet sich im Sinne eines "Eventualantrags" gegen das vorinstanzliche Strafmass. In vergleichbaren Fällen habe dieses praktisch nie das Mass von zwei Jahren überschritten. Er führt hierzu BGE 126 IV 126, 127 IV 86, 128 IV 106 sowie 132 IV 120 an.
3.6 Die Strafrechtliche Abteilung des Bundesgerichts greift auf Beschwerde in Strafsachen hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen beziehungsweise in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (vgl. BGE 134 IV 17 E. 2.1 mit Hinweisen).
Der Beschwerdeführer legt nicht dar, inwiefern dies der Fall sein sollte. Aus den von ihm angeführten Referenzfällen kann er ebenfalls nichts zu seinen Gunsten ableiten. Lediglich BGE 128 IV 106 und BGE 132 IV 120 haben die Strafzumessung zum Gegenstand. Im ersten Entscheid bestätigte das Bundesgericht eine Zuchthausstrafe von 3 1⁄4 Jahren für mehrfache sexuelle Handlungen mit Kindern und sexuelle Nötigung, im zweiten hob es eine bedingte Gefängnisstrafe von 3 Monaten für sexuelle Nötigung und Pornographie als unhaltbar milde auf und verlangte eine nicht wesentlich niedrigere Strafe wie sie für eine Vergewaltigung auszusprechen wäre. Die Rüge ist unbegründet.
4. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (Art. 66 Abs. 1 BGG). Der Beschwerdeführer ersucht um Gewährung der unentgeltlichen Rechtspflege. Da das Rechtsmittel von vornherein aussichtslos war, kann dem Gesuch nicht entsprochen werden (Art. 64 Abs. 1 BGG). Bei der Festsetzung der Gerichtskosten ist seinen finanziellen Verhältnissen Rechnung zu tragen.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Nidwalden, Strafabteilung Grosse Kammer, schriftlich mitgeteilt.
Lausanne, 14. Dezember 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller