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.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt hinsichtlich des Schuldspruchs wegen Raubs eine willkürliche Sachverhaltsfeststellung. Die von der Privatklägerin anlässlich der Berufungsverhandlungen gemachten Aussagen zum Tatablauf und zur Art und Weise der Gewaltanwendung wichen derart stark von denjenigen der polizeilichen Ersteinvernahme am Tattag ab, dass entgegen der Vorinstanz nicht von einer nachträglichen Verbesserung oder spontanen Präzisierung gesprochen werden könne. Die Privatklägerin schildere zwei verschiedene Geschehensabläufe, was zwingend zu erheblichen Zweifeln an der Richtigkeit ihrer Angaben führen müsse. Die Vorinstanz verharmlose die erkannten Widersprüche und verhalte sich zudem widersprüchlich. Sie habe im ersten, vom Bundesgericht aufgehobenen Berufungsurteil vom 13. März 2014 vollumfänglich auf die Erstaussagen der Privatklägerin vor der Polizei abgestellt und bezeichne diese jetzt als lediglich zusammenfassend, ohne Präzisierung und wegen des angeblichen Schockzustands als ungenau. Die Argumentation belege die mangelnde Objektivität der Vorinstanz bei der Würdigung der Aussagen der Privatklägerin. Deren Schilderung anlässlich der zweiten Berufungsverhandlung entspreche in auffälliger Weise dem Verletzungsbild des nachträglich von ihr eingereichten Arztzeugnisses.
Falle der Straftatbestand des Raubes weg, könne der Beschwerdeführer hinsichtlich des vorliegenden Vorfalls auch nicht wegen Diebstahls verurteilt werden. Die Privatklägerin sei nicht in der Lage, den genauen Deliktsbetrag zu benennen, ihre diesbezüglichen Einlassungen seien unpräzise und widersprüchlich. In Anwendung des Grundsatzes "in dubio pro reo" sei von einem Betrag von unter Fr. 300.- auszugehen. Mangels Strafantrags der Privatklägerin sei der Beschwerdeführer freizusprechen.
1.2. Die Vorinstanz erwägt, bezüglich der Gewaltanwendung gebe es einen gewissen Widerspruch zwischen den Aussagen der Privatklägerin anlässlich der (zweiten) Berufungsverhandlung und denjenigen bei der Polizei, wonach sie vom Beschwerdeführer mit dem Körper "weggecheckt" worden sei und einen heftigen Schlag gegen die linke Hüfte bekommen habe. Es sei jedoch zu berücksichtigen, dass die polizeiliche Befragung nur zusammengefasst wiedergegeben worden sei und die Privatklägerin bei der nur rund zwei Stunden nach dem Vorfall erfolgten Einvernahme unter Schock gestanden habe. Es sei verständlich, dass man sich in diesem Zustand nicht an alle Einzelheiten erinnern könne und sich mit der Zeit - auch aufgrund der sichtbaren Verletzungen - ein genaueres Bild des Geschehens mache, welches sich sehr schnell abgespielt habe. Das habe die Privatklägerin offensichtlich getan. Ihre anlässlich der zweiten Berufungsverhandlung gemachten Angaben, wonach sie mit "seinen Beinen oder so" einen Stoss gegen den Unterschenkel, links Innenseite, und einen gegen den Oberschenkel, links Oberseite, abbekommen habe, wirkten in der Grundaussage klar und glaubhaft. Die entsprechenden Hämatome seien denn auch durch ein wenige Tage später erstelltes Arztzeugnis belegt. Insgesamt habe sie glaubhaft und überzeugend dargelegt, dass der Beschuldigte sich durch Gewaltanwendung aus der ertappten Diebstahlsituation befreit habe. Die Privatklägerin habe nachvollziehbare Aussagen gemacht und dort Korrekturen angebracht, wo dies durchaus plausibel erscheine. Das Gericht sei deshalb nach wie vor überzeugt, dass der Beschuldigte am Raubüberfall wie in der Anklageschrift umschrieben beteiligt gewesen sei. Daran bestünden bei objektiver Betrachtung keine Zweifel, weshalb für einen Freispruch in Anwendung des Grundsatzes "in dubio pro reo" auch nach Durchführung der zweiten Berufungsverhandlung kein Platz bleibe.
1.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig, das heisst willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 10.1 S. 445 mit Hinweisen; zum Begriff der Willkür <ref-ruling> E. 2.1 S. 18 f.; <ref-ruling> E. 3.2.5 S. 339; je mit Hinweisen) oder wenn sie 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>). Den kantonalen Instanzen steht bei der Beweiswürdigung ein weiter Spielraum des Ermessens zu. Willkür liegt nur vor, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren Beweiswürdigung beruht, d.h. wenn die Behörde in ihrem Entscheid von Tatsachen ausgeht, die mit der tatsächlichen Situation in klarem Widerspruch stehen oder auf einem offenkundigen Fehler beruhen. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling>7 E. 2.1; <ref-ruling> E. 5.1).
Für die Rüge der Willkür gelten erhöhte Begründungsanforderungen. Eine entsprechende Rüge muss klar vorgebracht und substanziiert begründet werden. Auf eine rein appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (vgl. Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; <ref-ruling> E. 2.3 S. 266 mit Hinweisen).
1.4.
1.4.1. Auf die Rügen, die der Beschwerdeführer gegen die vorinstanzliche Beweiswürdigung in Bezug auf die Wegnahme des Rucksacks und der darin enthaltenen Gegenstände der Privatklägerin erhebt, ist nicht einzutreten. Im Rückweisungsentscheid vom 25. September 2014 hielt das Bundesgericht fest, dass die Vorinstanz willkürfrei darauf schliessen durfte, dass der Beschwerdeführer den Rucksack samt Inhalt aus dem Fahrzeuginneren der Privatklägerin entwendet hat. Aufgrund der Bindungswirkung des Rückweisungsurteils war es der Vorinstanz und den Parteien - abgesehen von allenfalls zulässigen Noven - verwehrt, dem neuen Entscheid einen anderen als den bestätigten Sachverhalt zu Grunde zu legen (vgl. <ref-ruling> E. 3 S. 335 f.; Urteile 6B_535/2015 vom 26. August 2015 E. 1.1; 6B_296/2014 vom 20. Oktober 2014 E. 1.2.2). Die Wiedergabe der vorinstanzlichen Beweiswürdigung und Erwägungen zur Wegnahme der Wertgegenstände und der hiergegen erhobenen Rügen erübrigt sich somit.
1.4.2. Die vorinstanzliche Beweiswürdigung erweist sich im Ergebnis nicht als schlechterdings unhaltbar. Entgegen dem Vorbringen des Beschwerdeführers verharmlost oder übersieht die Vorinstanz nicht in unhaltbarer Weise die Abweichungen in den Aussagen der Beschwerdegegnerin 2, sondern setzt sich mit diesen auseinander. Zwar ist zutreffend, dass diese nicht erst anlässlich der Berufungsverhandlung vom 5. Juni 2015 erstmals detailliert zum Ablauf des Vorfalls befragt worden ist, sondern bereits während der rund 35-minütigen polizeilichen Befragung zum Tatablauf geäussert hat, der Beschwerdeführer habe sie "weggecheckt", sie wisse aber nicht wie. Dass ihre Aussagen anlässlich der Berufungsverhandlung mit denjenigen der polizeilichen Befragung nicht deckungsgleich waren, bedeutet jedoch nicht, dass die Vorinstanz in Willkür verfällt, wenn sie von einem tätlichen Angriff auf die Beschwerdegegnerin 2 ausgeht. Nach konstanter Rechtsprechung genügt für die Begründung von Willkür mithin nicht, dass das angefochtene Urteil mit der Darstellung der beschwerdeführenden Partei nicht übereinstimmt oder auch eine andere Lösung oder Würdigung vertretbar erscheint. Der Beschwerdeführer zeigt nicht auf, inwieweit die vorinstanzlichen Sachverhaltsfeststellungen offensichtlich unhaltbar sein und die vorhandenen Beweise andere Schlussfolgerungen geradezu aufdrängen sollen. Dass der Beschwerdeführer aufgrund der Widersprüche erhebliche Zweifel an der Richtigkeit der Angaben der Beschwerdegegnerin 2 hat, führt nicht dazu, dass die vorinstanzliche Beweiswürdigung im Ergebnis schlechterdings unhaltbar ist. Das Bundesgericht ist keine Appellationsinstanz, die eine freie Prüfung in tatsächlicher Hinsicht vornimmt und die vorinstanzliche Beweiswürdigung durch eine eigene als richtig oder naheliegender erachtete ersetzen kann. Der (implizit geltend gemachten) Verletzung des Grundsatzes "in dubio pro reo" kommt in der vom Beschwerdeführer angerufenen Funktion als Beweiswürdigungsregel im Verfahren vor Bundesgericht keine über das Willkürverbot von <ref-law> hinausgehende selbstständige Bedeutung zu (vgl. <ref-ruling> E. 7 S. 82 mit Hinweisen).
1.4.3. Was der Beschwerdeführer gegen seine Strafbarkeit wegen Diebstahls vorbringt, erweist sich als unzutreffend, soweit auf die weitgehend appellatorischen Sachverhaltsrügen zur Deliktshöhe überhaupt einzutreten ist. Er übersieht, dass die Privatklägerin Strafantrag gestellt hat (kantonale Akten, act. 113 f.) und sich zudem (nochmals) als Strafklägerin konstituiert hat (kantonale Akten, act. 252 f.). Zwar konnte die Privatklägerin den ihr gestohlenen Geldbetrag nicht exakt beziffern, jedoch hat sie konstant ausgesagt, dass ihr mindestens EUR 200.- und Fr. 100.- abhanden gekommen sind, womit die Geringwertigkeitsgrenze von <ref-law> überschritten ist.
2.
2.1. Der Beschwerdeführer wendet sich gegen den Schuldspruch wegen rechtswidrigen Aufenthalts gemäss Art. 115 Abs. 1 lit. b AuG. Er rügt eine Verletzung seines Anspruchs auf rechtliches Gehör. Der eingeholte Amtsbericht des Staatssekretariats für Migration (SEM [bis zum 31. Dezember 2014 Bundesamt für Migration]) sei nicht verwertbar, da die "Beamten" nicht einvernommen worden seien. Die Feststellungen der Vorinstanz, der Beschwerdeführer habe nichts unternommen, um die für die Ausreise erforderlichen Papiere zu beschaffen, werde bestritten. Die Feststellung, das algerische Konsulat hätte sich beim SEM gemeldet, wenn der Beschwerdeführer bei der Beschaffung von Reisedokumenten ernsthaft mitgewirkt hätte, sei willkürlich und dadurch widerlegt, dass das Konsulat auf die Anfrage durch die Vorinstanz gerade nicht reagiert habe.
2.2. Die Vorinstanz erwägt, der Amtsbericht des SEM sei ein gemäss <ref-law> verwertbares Beweismittel. Das algerische Konsulat reagiere grundsätzlich (nur) auf Identifizierungsanträge des SEM. Dem Bericht sei zu entnehmen, dass im angeklagten Zeitraum keine Aktivitäten zur Papierbeschaffung registriert seien, weshalb davon auszugehen sei, der Beschwerdeführer verletze seit Dezember 1998 seine Mitwirkungspflichten. Anlässlich einer zentralen Befragung beim SEM im Dezember 2014, an der auch Vertreter des algerischen Konsulats zugegen waren, habe er jegliche Kooperation zur Feststellung seiner (wahren) Identität verweigert. Eine Rückreise in sein Heimatland wäre nach Auskunft des SEM problemlos möglich gewesen, wenn der Beschwerdeführer kooperiert hätte.
2.3. Die Einwände des Beschwerdeführers sind unbegründet, soweit überhaupt auf sie einzutreten ist. Er legt nicht dar, inwieweit eine Befragung der Beamten des SEM erforderlich gewesen sein soll und welche über die im Amtsbericht hinausgehenden Informationen die Beamten hätten liefern können. Dies ist auch nicht ersichtlich. Die Rügen gegen die aus dem Amtsbericht gezogenen Schlüsse erweisen sich als rein appellatorisch. Der Beschwerdeführer setzt sich mit der vorinstanzlichen Beweiswürdigung nicht auseinander, sondern beschränkt sich darauf, seinen im Berufungsverfahren vertretenen Standpunkt zu wiederholen und die Sachverhaltsfeststellungen zu bestreiten. Dies ist ungeeignet, um Willkür in der vorinstanzlichen Beweiswürdigung aufzuzeigen. Die Vorinstanz durfte willkürfrei darauf schliessen, dass es dem Beschwerdeführer möglich gewesen wäre, die für die Ausreise erforderlichen Dokumente zu beschaffen, er dies aber unterlassen bzw. durch seine verweigerte Mitwirkung verunmöglicht hat. Der Schuldspruch wegen rechtswidrigen Aufenthalts gemäss Art. 115 Abs. 1 lit. b AuG verletzt kein Bundesrecht.
3.
Die Anträge auf Entschädigung, Genugtuung und Herausgabe des bei ihm sichergestellten Bargelds begründet der Beschwerdeführer lediglich implizit mit den beantragten Freisprüchen. Da es bei den Schuldsprüchen bleibt, ist auf die Anträge nicht weiter einzugehen.
4.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Das Gesuch um unentgeltliche Rechtspflege ist, soweit die Rechtsbegehren nicht aussichtlos waren, teilweise gutzuheissen. Der Beschwerdeführer ist insoweit aus der Gerichtskasse zu entschädigen (<ref-law>). Soweit infolge Aussichtslosigkeit der Rechtsbegehren keine unentgeltliche Rechtspflege zu gewähren ist, sind die Gerichtskosten dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 64 Abs. 1 i.V.m. <ref-law>). Seiner finanziellen Lage ist bei der Bemessung der Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird teilweise gutgeheissen und im Übrigen abgewiesen. Für das bundesgerichtliche Verfahren wird dem Beschwerdeführer Rechtsanwalt Werner Greiner als unentgeltlicher Anwalt beigegeben.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt.
4.
Der Rechtsvertreter des Beschwerdeführers wird aus der Bundesgerichtskasse mit Fr. 1'500.- entschädigt.
5.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 19. April 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Held