Sachverhalt: A. Die Staatsanwaltschaft des Kantons Schaffhausen wirft dem algerischen Staatsangehörigen X._ vor, er habe gemeinsam mit seinem Bekannten Y._ den Entschluss gefasst, jemanden zu bestehlen. Y._ habe die Kundin eines Supermarktes abgelenkt, nachdem diese ihre Einkäufe im Auto verstaut hatte und anschliessend den Einkaufswagen zur Sammelstelle zurückbrachte. X._ habe die Ablenkung ausgenutzt und aus dem unverschlossenen Auto einen Rucksack samt Inhalt im Wert von ca. Fr. 347.-- sowie aus einem Sichtmäppchen rund EUR 300.-- und Fr. 100.-- Bargeld entwendet. Als die Frau die Situation erkannte und zu ihrem Auto eilte, soll X._ sie zur Seite gestossen haben, um gemeinsam mit Y._ und der Beute zu flüchten. Die Frau habe bei dem Vorfall ein Hämatom am Ober- und Unterschenkel, einen Schock und anhaltende Schmerzen an der Hüfte erlitten. Zudem soll X._ trotz rechtskräftiger Verfügung, die Schweiz verlassen zu müssen, keine Bemühungen unternommen haben, um gültige Ausweispapiere zur Ausreise zu erhalten, und habe sich demnach vom 29. Juli 2012 bis zum 1. März 2013 unrechtmässig in der Schweiz aufgehalten. B. Das Obergericht des Kantons Schaffhausen verurteilte X._ im Berufungsverfahren wegen Raubes und rechtswidrigen Aufenthalts zu einer unbedingten Freiheitsstrafe von 24 Monaten. Es verfügte die Herausgabe des anlässlich der Verhaftung bei ihm sichergestellten Bargelds von EUR 255.-- an die Autofahrerin. C. X._ führt Beschwerde in Strafsachen und beantragt, das obergerichtliche Urteil sei aufzuheben, und er sei vollumfänglich freizusprechen. Für die erlittene Untersuchungs- und Sicherheitshaft sei ihm eine angemessene Genugtuung zuzusprechen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. Das Obergericht hat auf eine Vernehmlassung verzichtet, die Geschädigte hat sich nicht vernehmen lassen. Die Staatsanwaltschaft beantragt, die Beschwerde abzuweisen.