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.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine Verletzung seines Anspruchs auf rechtliches Gehör und eine daraus resultierende willkürliche Sachverhaltsfeststellung. Er sei nie mit der Privatklägerin, deren Aussagen hinsichtlich des ihm zur Last gelegten Sachverhalts den einzigen Beweis bildeten, konfrontiert worden. Entgegen der Ansicht der Vorinstanz lasse sich der Anklagesachverhalt weder aufgrund der Aussagen des Mitbeschuldigten Y._ noch aufgrund der von der Privatklägerin eingereichten Kontoauszüge und ärztlichen Bescheinigungen nachweisen. Y._ habe den Anklagesachverhalt zwar teilweise eingeräumt, jedoch stets bestritten, dass es zu Tätlichkeiten gegenüber der Privatklägerin gekommen und der Beschwerdeführer an der Tat beteiligt gewesen sei. Das Arztzeugnis sei kein Indiz oder Beweis für die angebliche Gewaltanwendung, zumal die am linken Ober- und Unterschenkel festgestellten Hämatome nicht mit der Sachverhaltsdarstellung der Privatklägerin vereinbar seien, der Beschwerdeführer habe sie an der Hüfte weggecheckt. Unzutreffend sei, dass er den Antrag auf Konfrontation verspätet gestellt habe. Hätte die Vorinstanz seinen Beweisantrag vom 27. Januar 2014 nicht abgelehnt und die Privatklägerin dann doch unvermittelt drei Tage vor der Berufungsverhandlung telefonisch vorgeladen, wären noch Ersatzmassnahmen zur Wahrung des Gehörsanspruchs möglich gewesen.
1.2. Die Vorinstanz erwägt, es sei aktenkundig, dass keine Konfrontationseinvernahme stattgefunden habe. Die Privatklägerin müsse noch einvernommen und der Verteidigung Gelegenheit gegeben werden, Ergänzungsfragen zu stellen. Die zur Berufungsverhandlung (von Amtes wegen) vorgeladene Privatklägerin sei jedoch gemäss Bestätigung ihres Hausarztes "aus gesundheitlichen, respektive psychischen Gründen seit längerer Zeit und für nicht absehbare unbestimmte Zeit, nicht einvernahmefähig". Dass die Privatklägerin nicht einvernommen werden könne, beruhe nicht auf mangelnder Sorgfalt der Gerichtsbehörden, denn der anwaltlich vertretene Beschwerdeführer habe sowohl im Untersuchungsverfahren als auch im erstinstanzlichen Gerichtsverfahren ausreichend Gelegenheit zur Stellungnahme gehabt, es jedoch unterlassen, einen rechtzeitigen und formgerechten Beweisergänzungsantrag zu stellen. Ein solcher sei erstmals im Berufungsverfahren und somit verspätet erfolgt. Zudem stütze sich der Schuldspruch nicht ausschliesslich auf die Aussagen der Privatklägerin, sondern werde auch durch diejenigen des Mitbeschuldigten Y._ sowie die ärztlich attestierten Blutergüsse und Hämatome bestätigt. Es lägen demnach besondere Umstände vor, die es erlaubten, den grundsätzlich unbedingten Konfrontationsanspruch des Beschwerdeführers einzuschränken. Die "polizeilichen Aussagen" der Privatklägerin seien beweismässig verwertbar. Die Privatklägerin habe nachvollziehbar ausgesagt und dort Korrekturen angebracht, wo es plausibel erscheine. Die Aussagen des Beschwerdeführers seien hingegen höchst widersprüchlich. Die Auswertung seines Mobiltelefons habe ergeben, dass er sich entgegen seiner Einlassungen zur Tatzeit am Tatort bzw. in dessen Nähe aufgehalten habe. Dass die Hämatome nicht an der Hüfte, sondern "weiter unten" verursacht worden seien, spreche nicht gegen die Schilderung der Privatklägerin, denn der Begriff "Hüfte" sei umgangssprachlich weiter gefasst als derjenige in der "Fachsprache".
1.3.
1.3.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig 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> und <ref-law>). Offensichtlich unrichtig ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 4.2 S. 234 mit Hinweisen). Willkür liegt vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist oder mit der tatsächlichen Situation in klarem Widerspruch steht (<ref-ruling> E. 3.2.5 S. 339; <ref-ruling> E. 7.1 S. 51, 305 E. 4.3). Auf eine rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.2.3 mit Hinweisen).
1.3.2. Die Parteien haben Anspruch auf rechtliches Gehör (<ref-law>). Dazu gehört insbesondere der in <ref-law>, <ref-law> und Art. 6 Ziff. 3 lit. d EMRK garantierte Anspruch, Fragen an die Belastungszeugen zu stellen oder stellen zu lassen. Eine belastende Zeugenaussage ist danach grundsätzlich nur verwertbar, wenn die beschuldigte Person wenigstens einmal während des Verfahrens angemessene und hinreichende Gelegenheit hatte, das Zeugnis in Zweifel zu ziehen und Ergänzungsfragen zu stellen (<ref-ruling> E. 3.1 S. 41; <ref-ruling> E. 2.2 S. 480; je mit Hinweisen).
Dem Konfrontationsanspruch kommt grundsätzlich absoluter Charakter zu (BGE <ref-ruling> E. 2.2 S. 481; <ref-ruling> E. 3.1). Auf eine Konfrontation der beschuldigten Person oder auf eine ergänzende Befragung von Belastungszeugen/Auskunftspersonen kann nur unter besonderen Umständen verzichtet werden, etwa wenn diese berechtigterweise das Zeugnis verweigern, wenn sie trotz angemessener Nachforschungen unauffindbar bleiben, dauernd oder für lange Zeit einvernahmeunfähig werden oder wenn sie verstorben sind. Ausserdem darf der Umstand, dass die beschuldigte Person ihre Rechte nicht (rechtzeitig) wahrnehmen konnte, nicht in der Verantwortung der Behörde liegen (BGE <ref-ruling> E. 2.2 und 2.3.4 mit Hinweisen). Die Behörden müssen sich angemessen und gewissenhaft darum bemüht bzw. das Erforderliche unternommen haben, um die einzuvernehmende Person zur Aussage zu veranlassen, d.h. diese vorgeladen bzw. vorgeführt haben (Urteil 6B_255/2008 vom 10. Oktober 2008 E. 2.3.3 mit Hinweis), und zwar unabhängig davon, ob das streitige Zeugnis den einzigen oder einen wesentlichen Beweis darstellt (Urteil 6B_125/2012 vom 28. Juni 2012 E. 3.3.1 mit Hinweisen).
1.4.
1.4.1. Die Vorinstanz konnte insbesondere aufgrund der Ortung des Mobiltelefons und der widersprüchlichen Einlassungen des Beschwerdeführers willkürfrei darauf schliessen, er sei der Täter gewesen, der den Rucksack samt Inhalt aus dem Fahrzeuginneren der Privatklägerin entwendet hat. Der Beschwerdeführer setzt sich mit den diesbezüglichen Erwägungen der Vorinstanz nicht auseinander. Er zeigt nicht auf, inwieweit die Sachverhaltsfeststellungen unhaltbar sein sollen und sich ein anderes Beweisergebnis geradezu aufdrängt. Für die Rüge einer willkürlichen Beweiswürdigung genügt es vor Bundesgericht nicht, dass der Beschwerdeführer sich darauf beschränkt darzulegen, wie seiner Auffassung nach die vorhandenen Beweise richtigerweise zu würdigen gewesen wären.
1.4.2. Die Rüge, es sei nicht erstellt, dass die Privatklägerin vom Beschwerdeführer zur Seite gestossen wurde, ist begründet. Die Vorinstanz verhält sich widersprüchlich, wenn sie einerseits die persönliche Befragung der Privatklägerin für erforderlich erachtet und diese von Amtes wegen zur Berufungsverhandlung vorlädt, andererseits jedoch ohne nähere Begründung, warum deren Befragung für den Schuldspruch wegen Raubes nicht mehr erforderlich gewesen sein soll, auf die Einvernahme verzichtet. Sie verkennt zudem, dass bei "Aussage gegen Aussage"-Situationen grundsätzlich die unmittelbare Wahrnehmung durch das Gericht erforderlich ist. Andernfalls beruht die Aussagewürdigung auf einer unvollständigen Grundlage, was bei sich widersprechenden Angaben umso stärker ins Gewicht fällt (Urteile 6B_856/2013 vom 3. April 2014 E. 2.2; 6B_718/2013 vom 27. Februar 2014 E. 2.5; je mit Hinweisen; vgl. auch <ref-law>). Dies gilt vorliegend insbesondere deshalb, weil die Privatklägerin ausschliesslich im Ermittlungsverfahren durch die Polizei befragt wurde. Die Sachverhaltsfeststellung erweist sich demnach als unvollständig.
1.4.3. Zudem verletzt die Vorinstanz den Konfrontationsanspruch des Beschwerdeführers. Dieser hat sein Recht auf Ergänzungsfragen nicht dadurch verwirkt, dass er die Konfrontation erst im Rahmen der Berufung beantragt hat (vgl. Urteil 6B_510/2013 vom 3. März 2014 E. 1.3.2 mit Hinweisen). Die Privatklägerin war aufgrund der gerichtlichen Vorladung verpflichtet, zur Berufungsverhandlung zu erscheinen. Die Vorinstanz konnte im Hinblick auf die Beurteilung der Einvernahmefähigkeit nicht unbesehen auf das Zeugnis des Hausarztes der Privatklägerin abstellen. Der zweizeilige, nicht begründete "Krankheitsbefund", die Privatklägerin sei "aus gesundheitlichen, resp. psychischen Gründen seit längerer Zeit und für nicht absehbare Zeit nicht einvernahmefähig" erlaubt nicht, (für längere Zeit) auf die gerichtliche Einvernahme der Privatklägerin zu verzichten. Auch wenn die dem Beschwerdeführer zur Last gelegten Taten für die Privatklägerin schockierend gewesen sein mögen, ist für den medizinischen Laien nicht ohne Weiteres verständlich, dass eine Einvernahme auf nicht absehbare Zeit unmöglich sein soll. Das Arztzeugnis stellt keine medizinische Diagnose, die es dem Gericht im Rahmen der Plausibilitätskontrolle ermöglicht, die attestierte Einvernahmeunfähigkeit nachzuvollziehen. Posttraumatische Belastungsstörungen heilen in der Regel mit der Zeit ab; nur in wenigen Fällen kommt es zu einem chronischen, über viele Jahre dauernden Krankheitsverlauf (vgl. Urteil 6B_29/2008 vom 10. September 2008 E. 2.2.2). Die Beanspruchung durch eine kurze Befragung anlässlich der Berufungsverhandlung ist vergleichbar mit jener eines eingehenden Arztgesprächs mit ärztlicher Untersuchung. Auch die von der Privatklägerin gegenüber dem Vorsitzenden der Vorinstanz geäusserten (posttraumatischen) Belastungen wie Verfolgungsangst und Schlaflosigkeit sind keine Gründe, die eine zeitlich beschränkte Einvernahme durch das Gericht ausschliessen. Nicht nachvollziehbar ist zudem, warum die Privatklägerin trotz bereits länger bestehender Beschwerden keine ärztliche oder psychologische Hilfe in Anspruch nimmt.
Dass eine Einvernahme für die Privatklägerin mit gewissen Anstrengungen und Unannehmlichkeiten verbunden ist, rechtfertigt nicht, diese ohne eingehende Untersuchung durch einen kantonalen Bezirksarzt bzw. Psychiater dauerhaft von ihrer gesetzlichen Aussagepflicht zu dispensieren. Angesichts des dem Beschwerdeführer zur Last gelegten Verbrechens überwiegt das öffentliche Interesse an der Strafverfolgung jenes der Privatklägerin, möglichst nicht mehr durch das Strafverfahren belästigt zu werden. Den Interessen der Privatklägerin ist durch geeignete organisatorische Schutzmassnahmen und technische Vorkehrungen unter Wahrung der Verteidigungsrechte Rechnung zu tragen (vgl. Art. 149-156 StPO).
2.
2.1. Der Beschwerdeführer wendet sich gegen seine Verurteilung wegen rechtswidrigen Aufenthalts in der Schweiz gemäss Art. 115 Abs. 1 lit. b AuG. Entgegen der vorinstanzlichen Behauptung seien seine Angaben, welche Bemühungen er unternommen habe, um Ausweis- respektive Reisepapiere zu bekommen, nicht vage. Seine Angaben, im Jahre 2011 bei der algerischen Botschaft in Bern und im Dezember 2012 auf dem Konsulat in Genf vorstellig geworden zu sein, hätten ohne Weiteres überprüft werden können. Es sei zudem bekannt, dass die algerischen Behörden bei der Ausstellung von Dokumenten und der Rückschaffung von Asylbewerbern wenig bis überhaupt nicht kooperativ seien. Da er nicht habe nachweisen können, algerischer Staatsangehöriger zu sein, seien ihm keine Papiere ausgestellt worden.
2.2. Die Vorinstanz erwägt, der Beschwerdeführer habe für die Zeit nach seiner Haftentlassung am 29. Juli 2012 keinerlei ernsthafte Bemühungen glaubhaft gemacht, die seinen Willen dokumentierten, die Schweiz verlassen zu wollen. Es sei bei reinen Behauptungen geblieben, die durch keine objektiven Anhaltspunkte belegt seien. Es sei nicht Aufgabe der Staatsanwaltschaft, vage behauptete und nicht dokumentierte Bemühungsversuche zu widerlegen.
2.3. Gemäss Art. 116 Abs. 1 lit. b AuG wird mit Freiheitsstrafe bis zu einem Jahr oder Geldstrafe bestraft, wer sich rechtswidrig, namentlich nach Ablauf des bewilligungsfreien oder des bewilligten Aufenthalts, in der Schweiz aufhält.
2.4. Die Behauptung des Beschwerdeführers, er habe sich mehrmals vergeblich bei den algerischen Vertretungen in der Schweiz und durch seine Freundin bei den Behörden in Algerien um gültige Ausweis- und Reisedokumente bemüht, betrifft eine der freien Beweiswürdigung unterliegenden Tatfrage, die das Bundesgericht grundsätzlich nur auf Willkür überprüft. Dies entbindet die Strafbehörden jedoch nicht, von Amtes wegen alle für die Beurteilung der Tat und der beschuldigten Person bedeutsamen Tatsachen abzuklären und den hierbei belastenden und entlastenden Umständen mit gleicher Sorgfalt nachzugehen (<ref-law>). Ob die Vorbringen des Beschwerdeführers, er sei im Jahre 2011 bei der algerischen Botschaft in Bern und im Dezember 2012 auf dem Konsulat in Genf vorstellig geworden, derart vage sind, dass weder die Beschwerdegegnerin noch die kantonalen Gerichte diese hätten überprüfen können (und müssen), erscheint zumindest mit Hinblick auf den Konsulatsbesuch fragwürdig, kann jedoch offen bleiben. Eine Bestrafung wegen rechtswidrigen Aufenthalts nach Art. 116 Abs. 1 lit. b AuG setzt voraus, dass die Ausreise objektiv möglich ist (Urteile 6B_713/2012 vom 19. April 2013 E. 1.4; 6B_482/2010 vom 7. Oktober 2010E. 3.2.2 und 3.2.3). Die Vorinstanz äussert sich hierzu nicht und zeigt nicht auf, ob es dem Beschwerdeführer möglich gewesen wäre, die für eine Rückkehr nach Algerien erforderlichen Dokumente erhältlich zu machen. Damit verletzt sie Bundesrecht.
3.
Die Beschwerde ist gutzuheissen, soweit darauf eingetreten werden kann. Es sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist gegenstandslos. Der Kanton Schaffhausen hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Die Entschädigung ist praxisgemäss dem Rechtsvertreter auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Obergerichts des Kantons Schaffhausen vom 13. März 2014 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Schaffhausen hat den Vertreter des Beschwerdeführers, Rechtsanwalt Werner Greiner, für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Schaffhausen schriftlich mitgeteilt.
Lausanne, 25. September 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Held