Sachverhalt:
A. A.a Das Obergericht des Kantons Schaffhausen sprach X._ am 17. Februar 2012 im Berufungsverfahren der sexuellen Handlung mit einem Kind, der sexuellen Nötigung und der groben Verletzung der Verkehrsregeln schuldig. Es verurteilte ihn zu einer bedingten Freiheitsstrafe von 16 Monaten und zu einer Busse von Fr. 400.--. Die Schadenersatzforderung von Y._ von Fr. 543.-- hiess es gut und sprach ihr eine Genugtuung von Fr. 3'000.-- zu.
A.b Den Schuldsprüchen wegen sexueller Handlung mit einem Kind und sexueller Nötigung liegt folgender Sachverhalt zugrunde:
Y._ (geboren am xx. xx 1997) spielte an einem Nachmittag ca. Mitte Juni 2004 vor dem Wohnhaus von X._ in A._. Dieser verrichtete gerade Arbeiten als Hauswart und sagte ihr, sie solle zu ihm in den Keller kommen, was sie tat. Er verschloss die Türe des Kellerraums mit einem Schlüssel, setzte Y._ auf einen Holztisch, küsste sie auf die Wange und fragte sie, welche Farbe ihre Unterhose habe. Y._ sagte nichts. Daraufhin zog ihr X._ die Unterhose aus, küsste sie auf die Scheide und erklärte ihr, sie dürfe es ihren Eltern nicht sagen. Er gab ihr sodann 10 Rappen. Als jemand nach ihm rief, schloss er die Türe wieder auf und verliess mit Y._ den Kellerraum.
B. X._ führt Beschwerde in Strafsachen. Er beantragt, er sei von den Vorwürfen der sexuellen Nötigung und der sexuellen Handlung mit einem Kind freizusprechen und für die grobe Verletzung der Verkehrsregeln mit einer bedingten Geldstrafe von 30 Tagessätzen zu Fr. 10.-- zu bestrafen, bei einer Probezeit von zwei Jahren. Auf die Zivilforderungen sei nicht einzutreten, eventualiter seien diese abzuweisen. Für die ausgestandene Untersuchungshaft und die durch das Strafverfahren erlittenen psychischen und sozialen Beeinträchtigungen sei ihm eine Genugtuung von Fr. 16'000.-- zuzusprechen. Eventualiter sei die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.

Erwägungen:
1. 1.1 Der Beschwerdeführer rügt, Dr. B._ habe im Glaubhaftigkeitsgutachten seine Zusatzfrage nicht behandelt, ob ein Alternativszenario (insbesondere eine suggestive Beeinflussung der Beschwerdegegnerin 2 durch ihre Eltern) gegenüber der Anklageversion weniger wahrscheinlich, ebenso wahrscheinlich oder sogar wahrscheinlicher sei. Indem die Vorinstanz auf die mangelhafte Glaubhaftigkeitsanalyse abstelle, verletze sie seinen Anspruch auf rechtliches Gehör sowie das Fairnessgebot und den Grundsatz der Waffengleichheit.
1.2 Die Rüge ist unbegründet. Die Gutachterin gelangte zum Ergebnis, die Aussagen der Beschwerdegegnerin 2 enthielten viele Hinweise auf eine Erlebnisgrundlage (kant. Akten, Urk. 679). Sie prüfte, ob Anhaltspunkte für eine mögliche Falschbezichtigung bestehen und verneinte dies (kant. Akten, Urk. 679 ff.). Sie befasste sich namentlich mit der Frage nach einer suggestiven Beeinflussung durch die Eltern oder die Polizei, wobei sie ausführt, das vom Beschwerdeführer in der Berufungsverhandlung vorgetragene Alternativszenario lasse sich nicht stützen (kant. Akten, Urk. 680 f.). Auch konnte sie keine Hinweise für eine Verwechslung erkennen oder darauf, dass die Tatvorwürfe auf reinen Fantasien beruhen könnten (kant. Akten, Urk. 680). Damit nahm die Gutachterin zur Zusatzfrage des Beschwerdeführers Stellung. Eine Verletzung der angerufenen Bestimmungen der BV und der EMRK ist nicht ersichtlich.
2. 2.1 Der Beschwerdeführer wendet sich gegen die vorinstanzliche Beweiswürdigung. Die Vorinstanz beurteile seine Aussagen als nicht glaubhaft, da sie undifferenziert seien und verschiedene Unstimmigkeiten aufweisen würden. Sie lasse willkürlich unberücksichtigt, dass ihm im psychiatrischen Gutachten vom 29. März 2006 eine deutlich eingeschränkte Einvernahmefähigkeit attestiert worden sei, die sich in einer Beeinträchtigung des Erinnerungsvermögens sowie der Aussagetüchtigkeit infolge einer posttraumatischen Belastungsstörung ausdrücke. Willkürlich sei auch die vorinstanzliche Würdigung der Aussagen der Beschwerdegegnerin 2. Diese habe aufgrund der suggestiven Beeinflussung durch ihre Eltern nicht mehr zwischen Erlebtem und Nichterlebtem unterscheiden können und anlässlich der Einvernahme vom 16. Juli 2004 eine "Pseudoerinnerung" geschildert.
2.2 Die Sachverhaltsfeststellung der Vorinstanz kann vor Bundesgericht nur gerügt werden, wenn sie willkürlich (<ref-law>) ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 1.4.1). Willkür bei der Beweiswürdigung liegt vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist oder mit der tatsächlichen Situation in klarem Widerspruch steht. Dass eine andere Lösung oder Würdigung ebenfalls vertretbar oder gar zutreffender erscheint, genügt für die Annahme von Willkür nicht (<ref-ruling> E. 4.3; <ref-ruling> E. 2.4).
Die Rüge der Willkür muss präzise vorgebracht und begründet werden (<ref-law>). Der Beschwerdeführer muss im Einzelnen darlegen, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf eine rein appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.2.3; <ref-ruling> E. 2.8; je mit Hinweisen).
Die Rüge der Willkür muss präzise vorgebracht und begründet werden (<ref-law>). Der Beschwerdeführer muss im Einzelnen darlegen, inwiefern der angefochtene Entscheid an einem qualifizierten und offensichtlichen Mangel leidet. Auf eine rein appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.2.3; <ref-ruling> E. 2.8; je mit Hinweisen).
2.3 2.3.1 Die Vorinstanz äussert sich ausführlich zur Beweiswürdigung, wozu sie sich eingehend mit den Aussagen des Beschwerdeführers und der Beschwerdegegnerin 2 sowie deren Mutter und weiteren Personen auseinandersetzt (Urteil S. 6-49). Sie erachtet die Aussagen der Beschwerdegegnerin 2 als ausgesprochen glaubhaft. Diejenigen des Beschwerdeführers stuft sie als nicht glaubhaft ein (Urteil S. 48 f.).
2.3.2 Die vorinstanzliche Würdigung ist nicht willkürlich. Die Vorbringen des Beschwerdeführers erschöpfen sich in einer unzulässigen appellatorischen Kritik. Dies trifft namentlich auf den Einwand zu, die Beschwerdegegnerin 2 habe eine "Pseudoerinnerung" wiedergegeben. Die Vorinstanz legt dar, weshalb der These des Beschwerdeführers nicht gefolgt werden kann, die Beschwerdegegnerin 2 habe nicht von selbst Erlebtem berichtet, sondern dem Plan ihrer Eltern folgend bewusst falsche Angaben gemacht (Urteil S. 33 f.). Sie weist willkürfrei darauf hin, dass deren Aussagen quantitativ und qualitativ recht detailliert (Urteil S. 18-21) und konstant sind. Sie habe die Geschehnisse gegenüber ihrer Mutter, der sie untersuchenden Ärztin und anlässlich der Einvernahme im Kern und in mehreren Details jeweils gleich geschildert (Urteil S. 21-23). Die Vorinstanz befasst sich zudem mit den weiteren Realitätskriterien und gelangt zur Überzeugung, diese seien ebenfalls gegeben (Urteil S. 24-31). Der Beschwerdeführer beschränkt sich darauf, der vorinstanzlichen Sachverhaltsfeststellung seine eigene Würdigung gegenüberzustellen. Inwiefern der angefochtene Entscheid an einem offensichtlichen Mangel leidet, tut er nicht dar.
2.3.3 Gemäss dem psychiatrischen Gutachten vom 29. März 2006 finden sich keine eindeutigen Hinweise für eine verminderte Schuldfähigkeit des Beschwerdeführers im Zeitpunkt der Tat. Hingegen sei dieser "aktuell" psychisch und intellektuell nicht in der Lage, einer differenzierten Fragestellung zu folgen, diese ausreichend zu erfassen und zu verstehen oder differenziert darauf zu antworten. Vor dem Hintergrund der "aktuellen" psychischen Störung sei dessen Erinnerungsvermögen zurzeit als deutlich beeinträchtigt zu beurteilen (kant. Akten, Urk. 312). Diesen Ausführungen des Gutachters können keine Hinweise entnommen werden, dass sich die fehlende Einvernahmefähigkeit des Beschwerdeführers auf das gesamte Untersuchungsverfahren erstreckt.
Der Beschwerdeführer wurde im Juli 2004 mehrmals polizeilich einvernommen (kant. Akten, Urk. 37 ff.). Untersuchungsrichterliche Einvernahmen fanden am 15. und 20. Juli 2004 sowie am 26. April 2005 und am 26. Februar 2008 statt. Anhaltspunkte, dass der Beschwerdeführer bereits zu Beginn des Untersuchungsverfahrens nicht einvernahmefähig war, fehlen auch in den Einvernahmeprotokollen aus dem Jahre 2004. Aus dem Protokoll vom 26. April 2005 geht hervor, dass dieser damals gesundheitliche Probleme hatte. Er wurde von der Untersuchungsrichterin darauf aufmerksam gemacht, dass er sie wissen lassen müsse, wenn er nicht in der Lage sei, der Befragung zu folgen, was er anfänglich verneinte. Die Einvernahme wurde schliesslich vorzeitig beendet und beschlossen, die Einvernahmefähigkeit des Beschwerdeführers ärztlich abklären zu lassen (kant. Akten, Urk. 241 ff.). Dr. C._ erklärte den Beschwerdeführer am 25. Januar 2008 trotz überdurchschnittlich schneller Ermüdbarkeit und unterdurchschnittlicher emotioneller Belastbarkeit erneut für einvernahmefähig, woraufhin er zur Schlusseinvernahme vom 26. Februar 2008 vorgeladen wurde (kant. Akten, Urk. 232 und 252 ff.).
Die später aufgetretenen gesundheitlichen Probleme des Beschwerdeführers können entgegen dessen Auffassung nicht zur Folge haben, dass seine Aussagen zu Beginn der Untersuchung zwingend unverwertbar und einer Würdigung durch die Vorinstanz entzogen sind. Daran ändert nichts, dass die Probleme auf eine vorbestehende posttraumatische Belastungsstörung (Retraumatisierung) zurückzuführen waren (Beschwerde Ziff. 17 S. 8). Aus dem Einvernahmeprotokoll vom 26. April 2005 geht zudem hervor, dass der Beschwerdeführer selbst zum damaligen Zeitpunkt durchaus in der Lage war, Erinnerungslücken zu erkennen und zu kommunizieren (kant. Akten, Urk. 244). Im Übrigen setzt er sich mit der Argumentation der Vorinstanz nur ungenügend auseinander und legt nicht dar, weshalb deren Würdigung auch im Ergebnis offensichtlich falsch ist. Auf die unzureichend begründete Rüge ist nicht einzutreten.
3. 3.1 Der Beschwerdeführer bringt vor, die Vorinstanz hätte ihn vor der neuen Qualifikation der Tat als sexuelle Nötigung anhören müssen. Die Staatsanwaltschaft und die erste Instanz hätten lediglich eine Anwendung der Tatbestände der sexuellen Handlung mit einem Kind und der Schändung in Betracht gezogen. Er habe mit der rechtlichen Argumentation der Vorinstanz nicht rechnen müssen, er habe die Beschwerdegegnerin 2 durch Überrumpeln und Abschliessen der Kellertüre im Sinne von <ref-law> zum Widerstand unfähig gemacht.
3.2 Die Vorinstanz kommt entgegen der ersten Instanz zum Schluss, ausser der sexuellen Handlung mit einem Kind sei nicht zusätzlich der Tatbestand der Schändung, sondern derjenige der sexuellen Nötigung erfüllt, da der Beschwerdeführer die Widerstandsunfähigkeit selber herbeigeführt habe. Einer Verurteilung nach <ref-law> stehe kein prozessuales Hindernis entgegen. Das Gesetz sehe für die sexuelle Nötigung und die Schändung die gleiche Strafandrohung vor. Das Gericht sei an die rechtliche Beurteilung in der Anklageschrift nicht gebunden (Urteil S. 49 f.).
3.3 Am 1. Januar 2011 trat die Schweizerische Strafprozessordnung (StPO; SR 312.0) in Kraft. Das erstinstanzliche Urteil erging am 11. November 2008. Das Verfahren richtet sich daher nach der bis am 31. Dezember 2010 geltenden Strafprozessordnung vom 15. Dezember 1986 für den Kanton Schaffhausen (StPO/SH; <ref-law>; <ref-ruling> E. 1.1 mit Hinweisen).
Das neue Recht enthält eine klare Bestimmung zum Vorgehen bei einer Veränderung des rechtlichen Beurteilungsgesichtspunktes. Könnte nach Auffassung des Gerichts der in der Anklageschrift umschriebene Sachverhalt einen anderen Straftatbestand erfüllen, gibt es der Staatsanwaltschaft Gelegenheit die Anklage zu ändern, soweit diese unvollständig ist (<ref-law>). Ist die Anklageschrift aber auch hinsichtlich dieses anderen Straftatbestands vollständig und will das Gericht den Sachverhalt lediglich rechtlich anders würdigen als die Staatsanwaltschaft in der Anklage, eröffnet es dies den anwesenden Parteien und gibt ihnen Gelegenheit zur Stellungnahme (<ref-law>).
Nach dem zum Zeitpunkt des angefochtenen Entscheids massgebenden Recht war das Obergericht bei der Überprüfung des erstinstanzlichen Urteils in tatsächlicher und rechtlicher Hinsicht frei und nicht an die von den Parteien gestellten Anträge gebunden (<ref-law>/SH; vgl. auch <ref-ruling> E. 2.7; <ref-ruling> E. 2a mit Hinweisen sowie <ref-law>/SH). Wollte es von der rechtlichen Würdigung in der Anklage abweichen, musste es der betroffenen Person gestützt auf <ref-law> das rechtliche Gehör gewähren, soweit diese mit der beabsichtigten neuen rechtlichen Würdigung nicht rechnen musste. Auf die Gewährung des rechtlichen Gehörs konnte ausnahmsweise verzichtet werden, wenn die vorgängige Anhörung zur veränderten rechtlichen Würdigung keine Auswirkungen auf die Ausübung der Verteidigungsrechte haben konnte (vgl. BGE <ref-ruling> E. 2d/bb mit Hinweisen).
3.4 Der Beschwerdeführer macht geltend, er habe im Berufungsverfahren an seinem Standpunkt festgehalten, wonach der Tatbestand der Schändung nicht erfüllt ist, selbst wenn die zur Anklage gebrachte Tathandlung als erstellt erachtet würde (Beschwerde Ziff. 32 S. 16). Bis zur Eröffnung des angefochtenen Urteils habe er nicht damit rechnen müssen, dass ihm zur Last gelegt werden könnte, er habe das Opfer durch ein Überrumpeln und das Abschliessen der Türe zum Widerstand unfähig gemacht.
Die beiden Straftatbestände der Schändung (<ref-law>) und der sexuellen Nötigung (<ref-law>) unterscheiden sich lediglich in Bezug auf die Ausnutzung einer bestehenden bzw. die Herbeiführung einer Widerstandsunfähigkeit des Opfers. Der Unrechtsgehalt ist weitgehend identisch und beide Straftatbestände sehen die gleiche Strafandrohung - Freiheitsstrafe bis zu zehn Jahren oder Geldstrafe - vor. Bei der Schändung nutzt der Täter eine ohne sein Zutun bestehende Urteils- oder Widerstandsunfähigkeit aus, während er bei der sexuellen Nötigung aktiv auf eine Beschränkung der Handlungsfreiheit des Opfers hinwirkt.
Bereits in der Anklageschrift vom 8. August 2008 hat die Staatsanwaltschaft darauf hingewiesen, dass der Beschwerdeführer die Türe des Geräteraums mit einem Schlüssel verschlossen und das Opfer auf einen Holztisch gesetzt hatte. Auf seine Fragen habe das Opfer keine Antwort gegeben. Aufgrund seines Alters habe es den sexuellen Charakter des Übergriffs nicht erkannt und sei überdies auch körperlich und seelisch nicht in der Lage gewesen, sich dagegen zu wehren (kant. Akten, Urk. 433). Vor Kantonsgericht und Obergericht bestritt der Beschwerdeführer generell die ihm zur Last gelegte Handlung, wies jede Nötigung von sich, indem er geltend machte, er habe das Opfer weder in den Keller gelockt noch habe er die Türe abgeschlossen, und stellte verschiedene Alternativhypothesen auf. Während das Kantonsgericht den Straftatbestand der Schändung bejahte, gelangte das Obergericht zur Auffassung, dass derjenige der sexuellen Nötigung erfüllt ist. Zur Begründung des Schuldspruchs stellte es ausschliesslich auf Sachverhaltselemente (Überrumpelung und Verschliessen der Türe) ab, die bereits in der Anklageschrift genannt wurden und sowohl im erstinstanzlichen wie auch im Berufungsverfahren seitens der Verteidigung thematisiert worden waren. Der Beschwerdeführer musste deshalb mit einer Änderung des rechtlichen Gesichtspunkts rechnen, falls das Gericht zur Auffassung gelangen sollte, es liege keine konstitutionelle, sondern eine situationsbedingte Widerstandsunfähigkeit des Opfers vor. Nachdem er ausführlich zur Frage der ihm zur Last gelegten nötigenden Handlungen Stellung bezogen hatte, konnte der unterlassene Hinweis auf die Veränderung des rechtlichen Beurteilungsgesichtspunktes keine Auswirkung auf seine Verteidigungsrechte haben. Nach der zum Zeitpunkt des angefochtenen Entscheids massgebenden Rechtslage liegt keine Verletzung des rechtlichen Gehörs vor.
4. Da es bei den Schuldsprüchen wegen sexueller Handlung mit einem Kind und sexueller Nötigung bleibt, erübrigt sich eine Behandlung der übrigen Anträge.
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist infolge Aussichtslosigkeit der Beschwerde abzuweisen (Art. 64 Abs. 1 und 2 BGG). Der finanziellen Lage des Beschwerdeführers ist bei der Festsetzung der Gerichtskosten Rechnung zu tragen (<ref-law>).
Der Beschwerdegegnerin 2 sind im bundesgerichtlichen Verfahren keine Kosten entstanden, weshalb ihr keine Parteientschädigung zuzusprechen ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 800.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 5. Februar 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Unseld