Sachverhalt:
A. Das Bezirksgericht Zürich verurteilte am 28. April 2009 X._ wegen Schändung zum Nachteil von A._ mit einer unbedingten Freiheitsstrafe von 18 Monaten, unter Anrechnung von 164 Tagen Haft. Das Gericht stellte ausserdem die dem Grundsatz nach bestehende Schadenersatzpflicht von X._ fest. Zur genauen Feststellung des Umfangs des Schadenersatzanspruchs verwies es A._ auf den Zivilweg. Weiter verpflichtete es X._ zu einer Genugtuungszahlung von Fr. 8'000.-- zuzüglich Zinsen an A._.
B. X._ erhob Berufung an das Obergericht des Kantons Zürich. Dieses bestätigte mit Urteil vom 12. Januar 2010 das erstinstanzliche Urteil.
C. X._ führt Beschwerde in Strafsachen beim Bundesgericht. Er verlangt, das vorinstanzliche Urteil sei aufzuheben, und er sei vollumfänglich freizusprechen. Ferner sei auf die adhäsionsweise geltend gemachte Zivilforderung nicht einzutreten.
Ausserdem sei ihm die unentgeltliche Rechtspflege zu bewilligen und ihm Matthias Brunner als unentgeltlicher Rechtsbeistand zu bestellen.
D. Die Vorinstanz sowie die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung. A._ beantragt, die Beschwerde sei abzuweisen und das vorinstanzliche Urteil unter Kosten- und Entschädigungsfolgen zulasten des Beschwerdeführers zu bestätigen.

Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
Der Beschwerdeführer (geb. 26. April 1976), die Beschwerdegegnerin 2 (geb. 13. März 1991) und deren Freund sowie weitere Personen hörten am 12. November 2008 in der Wohnung des Beschwerdeführers in Zürich Musik, schauten einen Film und tranken reichlich Bier. Nachdem die weiteren Personen nach Hause gegangen waren, verliess der Beschwerdeführer kurzzeitig die Wohnung, um zusätzliches Bier zu kaufen. In dieser Zeit hatte die Beschwerdegegnerin 2 mit ihrem Freund im Badezimmer der Wohnung Geschlechtsverkehr. Sie legten sich anschliessend ins Bett und schliefen ein. Der Beschwerdeführer legte sich nach seiner Rückkehr ebenfalls in dieses Bett neben die dort schlafende Beschwerdegegnerin 2 . Nachdem sie ein Rütteln am Bett bemerkt hatte, spürte sie etwas am linken Oberschenkel und dass jemand auf ihr lag. Sie dachte, dass es ihr Freund war und wollte ihn umarmen. Als sie die Augen öffnete, befand sich jedoch der Beschwerdeführer auf ihr, wobei sie sein feuchtes, erigiertes Glied an der Innenseite ihres linken Oberschenkels spürte. Nachdem sie die Situation realisiert hatte, stiess sie den Beschwerdeführer von sich, umhüllte sich mit der Bettdecke und ging ins Badezimmer. Ihr Freund folgte ihr dorthin, wobei sie ihn unter Tränen immer wieder gefragt hat, warum er dies zugelassen habe. Nach einiger Zeit gingen sie ins Zimmer zurück, zogen sich an und verliessen die Wohnung, während der Beschwerdeführer versuchte, die Beschwerdegegnerin 2 zu trösten.
2. 2.1 Der Beschwerdeführer rügt, dass sich die Vorinstanz nicht mit seinen Vorbringen anlässlich der Berufungsverhandlung bezüglich des nicht erfüllten subjektiven Tatbestands der Schändung auseinandergesetzt habe. Sie mache denn auch überhaupt keine Ausführungen zum subjektiven Tatbestand. Er werde nicht ansatzweise in die Lage versetzt zu erkennen, aufgrund welcher Überlegungen die Vorinstanz zum Schluss gelangt sei, dass er gewusst habe, ob die Beschwerdegegnerin 2 geschlafen und die Umarmung nicht ihm gegolten habe. Im Rahmen der rechtlichen Würdigung befasse sich die Vorinstanz zwar auf ein paar Zeilen mit dem subjektiven Tatbestand. Eine Würdigung sei allerdings gar nicht möglich, da die Vorinstanz keine Erwägungen zu seinen inneren (Willens-) Vorgängen gemacht habe. Es mache den Anschein, dass das Urteil bereits vor der Hauptverhandlung geschrieben worden sei. Die Vorinstanz verletze damit den Anspruch auf rechtliches Gehör (Beschwerde, S. 6).
2.2 Das Bundesgericht hat wiederholt festgehalten, dass keine Verletzung des rechtlichen Gehör gemäss <ref-law> vorliegt, wenn sich die Vorinstanz nicht mit allen Argumenten des Beschwerdeführers auseinandersetzt (vgl. die jüngeren Urteile 6B_526/2009 vom 2. September 2009 E. 3.2 sowie 6B_678/2009 vom 3. November 2009 E. 5.2; ferner <ref-ruling> E. 3.1). Der Betroffene hat das Recht, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheids zur Sache zu äussern. Wesentlicher Bestandteil des Anspruchs auf rechtliches Gehör ist die Begründungspflicht. Diese soll verhindern, dass sich die Behörde von unsachlichen Motiven leiten lässt. Die Begründung erlaubt dem Betroffenen ausserdem, die Verfügung gegebenenfalls sachgerecht anzufechten. Dies ist nur möglich, wenn sowohl er wie auch die Rechtsmittelinstanz sich über die Tragweite des Entscheids ein Bild machen können. In diesem Sinn müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf welche sich ihr Entscheid stützt. Dies bedeutet indessen nicht, dass sie sich ausdrücklich mit jeder tatbeständlichen Behauptung und jedem rechtlichen Einwand auseinandersetzen muss. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (<ref-ruling> E. 3.1 mit Hinweisen). Die Begründungspflicht ist nicht verletzt, wenn die Vorinstanz ausdrücklich auf die Begründung der ersten Instanz verweist und diese zu ihrer eigenen macht.
2.3 Die Vorinstanz stellt die Aussagen der beteiligten Personen kurz dar (angefochtenes Urteil, S. 20 f.) und pflichtet im Übrigen der erstinstanzlichen Bewertung der Beweislage vollumfänglich bei. Es bestünden mit Ausnahme des Einführens von Fingern und des Geschlechtsteils keinerlei vernünftige Zweifel an der Sachverhaltsdarstellung gemäss Anklageschrift (angefochtenes Urteil, S. 22). Sie führt zum subjektiven Tatbestand im Rahmen der rechtlichen Würdigung anschliessend aus, die Beschwerdegegnerin 2 habe ihre Umarmung des Beschwerdeführers in der Aufwachphase als plausiblen Irrtum dargestellt. Aus der Umarmung ein zustimmendes Verhalten abzuleiten, so dass es am subjektiven Tatbestand der Schändung fehle, sei abwegig. Die Tathandlung der Schändung durch den Beschwerdeführer sei in diesem Zeitpunkt vielmehr bereits erfüllt gewesen. Ein subjektiver Vorsatz könne nicht im Nachhinein wegfallen (angefochtenes Urteil, S. 22).
2.4 Wer eine urteilsunfähige oder eine zum Widerstand unfähige Person in Kenntnis ihres Zustandes zum Beischlaf, zu einer beischlafsähnlichen oder einer anderen sexuellen Handlung missbraucht, wird mit Freiheitsstrafe bis zu zehn Jahren oder Geldstrafe bestraft (<ref-law>).
2.4 Wer eine urteilsunfähige oder eine zum Widerstand unfähige Person in Kenntnis ihres Zustandes zum Beischlaf, zu einer beischlafsähnlichen oder einer anderen sexuellen Handlung missbraucht, wird mit Freiheitsstrafe bis zu zehn Jahren oder Geldstrafe bestraft (<ref-law>).
2.5 2.5.1 Die Vorinstanz äussert sich bei einer Gesamtlänge ihres Urteils von insgesamt 34 Seiten nur gerade auf knapp einer halben Seite zum subjektiven Tatbestand der eingeklagten Schändungshandlung. Die Vorinstanz geht aufgrund der von ihr als überzeugend eingestuften erstinstanzlichen Beweiswürdigung, die sich auf die Aussagen der Beschwerdegegnerin 2 stützt, davon aus, dass sich der Beschwerdeführer nach seiner Rückkehr vom Bierholen in das Bett neben die dort schlafende Beschwerdegegnerin 2 gelegt habe. Die Frage, ob die Umarmung der Beschwerdegegnerin 2 nicht dem Beschwerdeführer gegolten habe, beantwortet die Vorinstanz, indem sie es als abwegig bezeichnet, aus der Umarmung ein zustimmendes Verhalten der Beschwerdegegnerin 2 abzuleiten.
2.5.2 Der Beschwerdeführer weist zutreffend darauf hin, dass die vorinstanzlichen Erwägungen die Frage unbeantwortet lassen, ob die Tathandlung wissentlich und willentlich erfolgt sei. Vom Willen der Beschwerdegegnerin 2 lässt sich jedenfalls entgegen der Vorinstanz nicht ohne weiteres auf die Absichten des Beschwerdeführers schliessen. Wenn sich die Beschwerdegegnerin 2 in einem plausiblen Irrtum im Zeitpunkt ihrer Umarmung befunden hat, kann die Vorinstanz nicht von vornherein und ohne weitere Begründung seinen Tatwillen bejahen, indem sie seine Behauptung als abwegig bezeichnet, wonach die Umarmung als Zustimmung zu deuten gewesen sei.
2.5.3 Das Argument der Vorinstanz, dass die Tathandlung im Zeitpunkt der Umarmung bereits erfüllt gewesen sei und der "subjektive Vorsatz" nicht im Nachhinein wegfallen könne, ist ebenfalls nicht stichhaltig, begründet sie doch den Vorsatz des Beschwerdeführers (wie erwähnt) gerade mit dem Umstand, dass sich die Beschwerdegegnerin 2 bei ihrer Umarmung (also nach seiner allfälligen Vorsatzbildung) in einem Irrtum befunden habe.
2.5.4 Die Vorinstanz verletzt den Anspruch des Beschwerdeführers auf rechtliches Gehör, indem sie sich mit seinen Vorbringen anlässlich der Hauptverhandlung nicht bzw. ungenügend auseinandersetzt und den subjektiven Tatbestand der eingeklagten Schändungshandlung nicht rechtsgenüglich nachgewiesen hat. Der Verweis der Vorinstanz auf <ref-ruling>, bei welchem Entscheid ein Irrtum identischer Art das Bundesgericht nicht dazu bewogen habe, den Vorsatz in Frage zu stellen, vermag hieran nichts zu ändern, zumal die Erfüllung des subjektiven Tatbestands im Einzelfall gesondert zu prüfen ist und der Sachverhalt im angeführten Präjudiz mit dem vorliegend festgestellten Sachverhalt nicht identisch ist.
Auf die übrigen Vorbringen des Beschwerdeführers ist bei dieser Sachlage nicht einzugehen.
3. Die Beschwerde ist gutzuheissen. Das angefochtene Urteil des Obergerichts des Kantons Zürich vom 12. Januar 2010 ist aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 i.V.m. Abs. 4 BGG). Das Gesuch um unentgeltliche Rechtspflege ist infolge Gutheissung der Beschwerde gegenstandslos geworden. Der Kanton Zürich hat dem Beschwerdeführer eine angemessene Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Das angefochtene Urteil des Obergerichts des Kantons Zürich vom 12. Januar 2010 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton Zürich hat dem Beschwerdeführer eine Parteientschädigung von Fr. 3'000.-- auszurichten.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 27. August 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller