Sachverhalt: A. Die Staatsanwaltschaft des Kantons Schaffhausen wirft dem algerischen Staatsangehörigen X._ vor, gemeinsam mit dem separat verfolgten Y._ einen räuberischen Diebstahl begangen zu haben. Y._ habe eine 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, um aus dem unverschlossenen Auto Wertsachen zu entwenden. Als die Kundin die Situation erkannte und zu ihrem Auto eilte, habe X._ sie zur Seite "gecheckt", um gemeinsam mit Y._ und der Beute von EUR 300.- und Fr. 100.- zu flüchten. Die Geschädigte habe bei dem Vorfall ein Hämatom am linken Ober- und Unterschenkel, einen Schock und anhaltende Schmerzen an der Hüfte erlitten. Zudem habe X._ sich nach Verbüssung einer Freiheitsstrafe vom 29. Juli 2012 bis zu seiner erneuten Verhaftung am 1. März 2013 unrechtmässig in der Schweiz aufgehalten, da er trotz rechtskräftiger Verfügung, die Schweiz zu verlassen, keine Bemühungen unternommen habe, um gültige Ausweispapiere für die Ausreise zu erhalten. B. Das Kantonsgericht Schaffhausen verurteilte X._ am 31. Oktober 2013 erstinstanzlich wegen Raubes und rechtswidrigen Aufenthalts zu einer unbedingten Freiheitsstrafe von 16 Monaten und ordnete an, das bei ihm sichergestellte Bargeld in Höhe von EUR 255.- an die Geschädigte herauszugeben. Das Obergericht des Kantons Schaffhausen verurteilte X._ im Berufungsverfahren wegen Raubes und rechtswidrigen Aufenthalts zu einer unbedingten Freiheitsstrafe von 24 Monaten und verfügte die Herausgabe des sichergestellten Bargelds in Höhe von EUR 255.- an die Geschädigte. Die hiergegen von X._ geführte Beschwerde in Strafsachen hiess das Bundesgericht am 25. September 2014 (Verfahren 6B_620/2014) wegen formeller Fehler teilweise gut, hob das obergerichtliche Urteil auf und wies die Sache zur Neubeurteilung zurück. C. Anlässlich der erneuten Berufungsverhandlung vom 5. Juni 2015 hörte das Obergericht die Geschädigte an und verurteilte X._ erneut wegen Raubes und rechtswidrigen Aufenthalts zu einer unbedingten Freiheitsstrafe von 24 Monaten. D. X._ beantragt mit Beschwerde in Strafsachen, das Urteil des Obergerichts sei aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Er sei von den Vorwürfen des Raubs und des rechtswidrigen Aufenthalts freizusprechen. Der sichergestellte Bargeldbetrag sei an ihn herauszugeben und er sei für die erlittene Untersuchungs- und Sicherheitshaft sowie für die private Verteidigung angemessen zu entschädigen. X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung. Das Obergericht verzichtet auf eine Vernehmlassung, die Geschädigte hat sich nicht geäussert. Die Staatsanwaltschaft des Kantons Schaffhausen beantragt in ihrer Vernehmlassung die Abweisung der Beschwerde. X._ hält in seiner Stellungnahme an seinen Anträgen fest.