Faits :
A.
Par jugement du 21 mai 2019, le Tribunal de police de l'arrondissement de la Broye et du Nord vaudois a reconnu A._ et B._ coupables d'escroquerie et les a libérés du chef de faux dans les titres. Il a condamné A._ à une peine pécuniaire de 45 jours-amende à 30 fr. l'unité, avec sursis pendant deux ans et a ordonné son expulsion du territoire suisse pour une durée de 5 ans.
B.
Par jugement du 9 septembre 2019, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel formé par A._ contre le jugement de première instance, qu'elle a confirmé.
En substance, elle a retenu les faits suivants.
B.a. A._, né en 1984, de nationalité somalienne, marié, a vécu dans son pays d'origine jusqu'en novembre 2008, date de son arrivée en Suisse. Son épouse et ses quatre enfants (âgés entre 11 et 14 ans) vivent en Somalie. Demandeur d'asile, sans formation, A._ est titulaire d'une admission provisoire (permis F). Il ne travaille pas, bénéficie de l'aide financière de l'Établissement vaudois d'accueil des migrants (ci-après: EVAM) et fait l'objet d'actes de défaut de biens et d'une poursuite.
B.b. En avril 2016, A._ a déclaré à l'EVAM qu'il avait trouvé un hébergement à C._ qu'il sous-louait à B._ pour un loyer mensuel de 1'000 francs. Se fondant sur un formulaire attestant la sous-location, l'EVAM a accepté de participer au paiement du loyer à hauteur forfaitaire de 619 fr. par mois et a versé à A._ la somme de 700 fr. pour ses frais de déménagement et de mobilier privé. A._ devait ensuite, tous les deux mois, remplir le formulaire " Commande d'assistance financière " (ci-après: CAF) et fournir un justificatif de loyer afin de continuer à bénéficier des prestations financières.
Du 1er mai 2016 au 28 février 2017, A._ a signé plusieurs CAF et produit des quittances signées, attestant du paiement d'un loyer à B._. L'EVAM, qui se trouvait dans l'impossibilité matérielle et logistique de procéder à des vérifications poussées pour chaque demande soumise, a systématiquement accordé la participation mensuelle de 619 fr. à A._.
Le 14 février 2017, B._ a dénoncé A._, soutenant que ce dernier n'avait en réalité jamais sous-loué son logement et qu'ils avaient tous deux convenu dès le départ que A._ lui verserait 200 fr. par mois (de la somme de 619 fr.) afin de pouvoir apposer son nom sur sa boîte aux lettres. A._ n'a versé les 200 fr. convenus qu'à sept reprises. A._ a fait l'objet de onze décisions de restitution pour un montant total de 6'561 fr. 40 qui n'a pas été remboursé. Le 2 mai 2017, l'EVAM a dénoncé A._ et B._, lesquels ont admis que le premier n'avait jamais logé chez le second.
C.
A._ forme un recours en matière pénale auprès du Tribunal fédéral contre la décision cantonale et conclut, avec suite de frais et dépens, à titre principal, à son acquittement et à ce qu'il est renoncé à son expulsion de Suisse. A titre subsidiaire, il conclut au renvoi de la cause à la cour cantonale. Il requiert par ailleurs l'octroi de l'effet suspensif ainsi que l'assistance judiciaire.

Considérant en droit :
1.
Le recourant conteste s'être rendu coupable d'escroquerie et s'en prend aux faits établis par la cour cantonale sur ce point.
1.1.
1.1.1. Le Tribunal fédéral n'est pas une autorité d'appel, auprès de laquelle les faits pourraient être rediscutés librement. Il est lié par les constatations de fait de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, soit pour l'essentiel de façon arbitraire au sens de l'art. 9 Cst. Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable et cela non seulement dans sa motivation mais aussi dans son résultat. Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire. La présomption d'innocence, garantie par les <ref-law>, 32 al. 1 Cst., 14 par. 2 Pacte ONU II et 6 par. 2 CEDH, ainsi que son corollaire, le principe " in dubio pro reo ", concernent tant le fardeau de la preuve que l'appréciation des preuves au sens large. En tant que règle sur le fardeau de la preuve, elle signifie, au stade du jugement, que ce fardeau incombe à l'accusation et que le doute doit profiter au prévenu. Comme règle d'appréciation des preuves, la présomption d'innocence signifie que le juge ne doit pas se déclarer convaincu de l'existence d'un fait défavorable à l'accusé si, d'un point de vue objectif, il existe des doutes quant à l'existence de ce fait. Il importe peu qu'il subsiste des doutes seulement abstraits et théoriques, qui sont toujours possibles, une certitude absolue ne pouvant être exigée. Il doit s'agir de doutes sérieux et irréductibles, c'est-à-dire de doutes qui s'imposent à l'esprit en fonction de la situation objective. Lorsque l'appréciation des preuves et la constatation des faits sont critiquées en référence au principe " in dubio pro reo ", celui-ci n'a pas de portée plus large que l'interdiction de l'arbitraire (<ref-ruling> consid. 1.1 p. 155 s. et les références citées).
1.1.2. Aux termes de l'<ref-law>, se rend coupable d'escroquerie celui qui, dans le dessein de se procurer ou de procurer à un tiers un enrichissement illégitime, aura astucieusement induit en erreur une personne par des affirmations fallacieuses ou par la dissimulation de faits vrais ou l'aura astucieusement confortée dans son erreur et aura de la sorte déterminé la victime à des actes préjudiciables à ses intérêts pécuniaires ou à ceux d'un tiers.
L'escroquerie consiste à tromper la dupe. Pour qu'il y ait escroquerie, une simple tromperie ne suffit cependant pas; il faut qu'elle soit astucieuse. Il y a tromperie astucieuse, au sens de l'<ref-law>, lorsque l'auteur recourt à un édifice de mensonges, à des manoeuvres frauduleuses ou à une mise en scène, mais aussi lorsqu'il donne simplement de fausses informations, si leur vérification n'est pas possible, ne l'est que difficilement ou ne peut raisonnablement être exigée, de même que si l'auteur dissuade la dupe de vérifier ou prévoit, en fonction des circonstances, qu'elle renoncera à le faire en raison d'un rapport de confiance particulier (<ref-ruling> consid. 2.2.2 p. 154 s.; <ref-ruling> consid. 5.2 p. 79 s.). L'astuce n'est pas réalisée si la dupe pouvait se protéger avec un minimum d'attention ou éviter l'erreur avec le minimum de prudence que l'on pouvait attendre d'elle. Il n'est cependant pas nécessaire qu'elle ait fait preuve de la plus grande diligence ou qu'elle ait recouru à toutes les mesures possibles pour éviter d'être trompée. L'astuce n'est exclue que si elle n'a pas procédé aux vérifications élémentaires que l'on pouvait attendre d'elle au vu des circonstances. Une co-responsabilité de la dupe n'exclut toutefois l'astuce que dans des cas exceptionnels (<ref-ruling> consid. 2.2.2 p. 155; <ref-ruling> consid. 5.2 p. 81).
La définition générale de l'astuce est également applicable à l'escroquerie en matière d'assurances et d'aide sociale. L'autorité agit de manière légère lorsqu'elle n'examine pas les pièces produites ou néglige de demander à celui qui requiert des prestations les documents nécessaires afin d'établir ses revenus et sa fortune, comme par exemple sa déclaration fiscale, une décision de taxation ou des extraits de ses comptes bancaires. En revanche, compte tenu du nombre de demandes d'aide sociale, une négligence ne peut être reprochée à l'autorité lorsque les pièces ne contiennent pas d'indice quant à des revenus ou à des éléments de fortune non déclarés ou qu'il est prévisible qu'elles n'en contiennent pas. En l'absence d'indice lui permettant de suspecter une modification du droit du bénéficiaire à bénéficier des prestations servies, l'autorité d'assistance n'a pas à procéder à des vérifications particulières (arrêts 6B_1255/2018 du 22 janvier 2019 consid. 1.1; 6B_392/2016 du 10 novembre 2016 consid. 2.1.2; 6B_117/2015 du 11 février 2016 consid. 23.2 et les références citées).
1.2. Avec les premiers juges, la cour cantonale s'est fondée sur les documents adressés par les intéressés à l'EVAM (formulaire de sous-location, CAF, quittances de loyer) et considéré qu'on ne pouvait exiger de ce dernier qu'il procède à de plus amples vérifications, puisqu'il devait gérer un nombre important de dossiers.
La cour cantonale a écarté la thèse du recourant, selon laquelle il n'avait pas saisi la portée des documents présentés, B._ s'occupant de tout. Elle a relevé que le recourant savait dès le départ qu'il n'habiterait pas dans l'appartement en question et que c'était sur la base du contrat de sous-location et des quittances de loyer simulés qu'il avait produits, que l'EVAM lui avait versé le montant mensuel de 619 fr. pour l'aide au logement. Le fait que le recourant eût procédé sans l'aide d'un interprète n'y changeait rien, puisqu'il avait admis qu'il n'avait en réalité jamais habité chez B._ et que cela ne lui avait posé aucun problème linguistique d'annoncer à l'EVAM qu'il avait trouvé un logement. La cour cantonale a considéré que cela était suffisant pour qualifier l'attitude du recourant d'astucieuse.
Le recourant ne pouvait pas se prévaloir du fait qu'il aurait logé chez des tiers et aurait de toutes façons perçu une aide de l'EVAM pour la période d'avril 2016 à février 2017, dès lors que l'aide financière au logement était uniquement octroyée parce qu'il était placé auparavant dans un abri PC - situation dans laquelle la personne assistée ne perçoit aucune prestation financière pour l'hébergement - et parce qu'il avait faussement indiqué qu'il disposait d'un bail à loyer privé. L'EVAM n'aurait pas versé un montant mensuel forfaitaire de 619 fr. et les frais de déménagement s'il avait connu la tromperie. En percevant pendant plus de dix mois l'aide au logement accordée aux personnes assistées disposant d'un bail à loyer, le recourant avait causé un dommage à l'Etat.
1.3. Le recourant livre sa propre appréciation des faits, notamment quant à ses intentions, au prix du logement, à la valeur probante des documents présentés à l'EVAM (qu'il qualifie de " bouts de papier ") ainsi qu'aux interrogations que cela aurait dû susciter auprès de ce dernier. Ce procédé, purement appellatoire, est irrecevable (cf. <ref-law>). Il en va notamment ainsi lorsque le recourant affirme, sans critiquer de manière précise la motivation cantonale topique, qu'il " aurait dû sauter aux yeux de l'EVAM que les documents signés (...) ne correspondait (sic!) ni à la situation réelle, ni à celle présentée " ou qu'il avait de toutes façons droit au paiement d'un loyer et que les 600 fr. de l'EVAM étaient dépensés pour bénéficier d'une adresse postale " pour sa correspondance " (200 fr. par mois) et pour loger chez des tiers " de la même tribu " (environ 400 fr. par mois).
La libre présentation, par le recourant, de faits précédant l'infraction (phase dépressive, recherche de logement et d'une adresse postale, etc.), qui ne ressortent pas de la décision cantonale, sans que l'arbitraire de leur omission ne soit invoqué ni motivé, est irrecevable (cf. <ref-law>).
Contrairement à ce que prétend le recourant, les premiers juges n'ont pas nié la valeur probante des attestations mensuelles de versement du loyer mais ont exclu leur qualification de titres. Il ne saurait ainsi rien déduire en sa faveur du jugement de première instance quant à l'appréciation de ces documents pour la réalisation de l'escroquerie, étant rappelé que les premiers juges ont précisément retenu ce chef d'infraction.
En tant que le recourant prétend qu'il avait droit à l'aide sociale, en se limitant à invoquer la tradition humanitaire suisse, il ne discute pas la motivation cantonale sur ce point et ne formule pas de grief suffisamment motivé (<ref-law>). En tout état, le recourant ne précise pas sur quelle base légale il aurait, de toutes façons, eu droit au montant de 619 fr. et n'invoque pas l'arbitraire dans l'application du droit cantonal sur la question de cette prétention.
Sous couvert d'une violation de l'<ref-law>, le recourant prétend qu'il n'y avait ni astuce, ni dommage, ni intention de porter préjudice. Ce faisant, il reprend la même argumentation que celle développée en lien avec l'établissement des faits et se fonde sur sa propre appréciation des pièces et de la situation. Il n'y a pas lieu d'entrer en matière sur ce point.
2.
Le recourant reproche à la cour cantonale d'avoir prononcé son expulsion du territoire suisse en violation de l'<ref-law>. Il considère qu'elle a fait preuve d'arbitraire dans les constatations de faits sur la situation en Somalie.
2.1. Aux termes de l'art. 66a al. 1 let. e CP, le juge expulse de Suisse l'étranger qui est condamné pour escroquerie (<ref-law>) à une assurance sociale ou à l'aide sociale, obtention illicite de prestations d'une assurance sociale ou de l'aide sociale (<ref-law>), quelle que soit la quotité de la peine prononcée à son encontre, pour une durée de cinq à quinze ans. Selon l'<ref-law>, le juge peut exceptionnellement renoncer à une expulsion lorsque celle-ci mettrait l'étranger dans une situation personnelle grave et que les intérêts publics à l'expulsion ne l'emportent pas sur l'intérêt privé de l'étranger à demeurer en Suisse. A cet égard, il tiendra compte de la situation particulière de l'étranger qui est né ou qui a grandi en Suisse.
2.2. En l'espèce, le recourant a commis une infraction (escroquerie) qui tombe sous le coup de l'art. 66a al. 1 let. e CP. Il remplit donc a priori les conditions d'une expulsion, sous la réserve d'une application de l'<ref-law>, voire également des normes de droit international.
2.3.
2.3.1. La loi ne définit pas ce qu'il faut entendre par une " situation personnelle grave " (première condition cumulative) ni n'indique les critères à prendre en compte dans la pesée des intérêts (seconde condition cumulative). En recourant à la notion de cas de rigueur dans le cadre de l'<ref-law>, le législateur a fait usage d'un concept ancré depuis longtemps dans le droit des étrangers. Compte tenu également du lien étroit entre l'expulsion pénale et les mesures du droit des étrangers, il est justifié de s'inspirer, de manière générale, des critères prévus par l'art. 31 al. 1 de l'ordonnance relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201) et de la jurisprudence y relative, dans le cadre de l'application de l'<ref-law>. L'art. 31 al. 1 OASA prévoit qu'une autorisation de séjour peut être octroyée dans les cas individuels d'extrême gravité. L'autorité doit tenir compte notamment de l'intégration du requérant selon les critères définis à l'art. 58a al. 1 de la loi fédérale sur les étrangers et l'intégration (LEI; RS 142.20), de la situation familiale, particulièrement de la période de scolarisation et de la durée de la scolarité des enfants, de la situation financière, de la durée de la présence en Suisse, de l'état de santé ainsi que des possibilités de réintégration dans l'Etat de provenance. Comme la liste de l'art. 31 al. 1 OASA n'est pas exhaustive et que l'expulsion relève du droit pénal, le juge devra également, dans l'examen du cas de rigueur, tenir compte des perspectives de réinsertion sociale du condamné (<ref-ruling> consid. 3.3.2 p. 340 s.; arrêt 6B_1045/2019 du 18 octobre 2019 consid. 1.3.1). En règle générale, il convient d'admettre l'existence d'un cas de rigueur au sens de l'<ref-law> lorsque l'expulsion constituerait, pour l'intéressé, une ingérence d'une certaine importance dans son droit au respect de sa vie privée et familiale garanti par la Constitution fédérale (art. 13 Cst.) et par le droit international, en particulier l'art. 8 CEDH (arrêts 6B_908/2019 du 5 novembre 2019 consid. 2.1; 6B_1045/2019 du 18 octobre 2019 consid. 1.3.1; 6B_925/2019 du 16 octobre 2019 consid. 1.1).
2.3.2. En l'occurrence, ainsi que l'a relevé la cour cantonale, le recourant est arrivé en Suisse à l'âge de 24 ans, il émarge depuis à l'aide sociale et n'a jamais travaillé. Il n'a pas d'autorisation de séjour, ne sait ni lire ni écrire et n'a pas de formation. Il prétend ne pas parler ni comprendre le français alors qu'il vit en Suisse depuis plus de 10 ans. Le recourant n'a pas non plus d'attaches familiales en Suisse. Selon ses propres déclarations en audience, sa famille ne risque pas pour sa vie ou sa santé là où elle se trouve en Somalie.
Les explications que fonde le recourant sur des pièces qui ne ressortent pas de la décision entreprise sont irrecevable (cf. <ref-law>). Il n'y pas lieu d'entrer en matière sur la présentation personnelle qu'il livre sur la situation générale en Somalie ainsi que dans les différentes régions du pays (<ref-law>). Le recourant est irrecevable à déclarer, à ce stade, qu'en sa " qualité d'homme d'obédience musulmane appartenant à une minorité ethnique sans soutien clanique ", sa situation serait complètement différente de celle de son épouse. La jurisprudence de l'ancienne commission de recours en matière d'asile, de 2006, dont il ressortirait une " situation chaotique et les incidents violents dans le centre et le sud de la Somalie " ne lui sont d'aucun secours, étant précisé qu'il a déclaré en audience d'appel que sa famille vivait dans le nord du pays, " région plutôt stable " (jugement cantonal p. 3). En tant que le recourant se contente d'affirmer que ces éléments auraient été mal protocolés lors des auditions, il ne remplit pas les exigences minimales de motivation, de sorte qu'il n'y a pas lieu d'entrer en matière sur ce point (cf. <ref-law>). Pour le surplus, le recourant ne saurait se prévaloir d'une situation grave fondée sur la seule " tradition humanitaire suisse ".
Le recourant ne saurait invoquer le respect de sa vie privée (art. 8 par. 1 CEDH) au motif qu'il aurait " noué des liens (...) avec des immigrés somaliens ", étant relevé que, selon la jurisprudence, l'étranger doit établir l'existence de liens sociaux et professionnels spécialement intenses avec la Suisse, notablement supérieurs à ceux qui résultent d'une intégration ordinaire (cf. arrêts 6B_2/2019 du 27 septembre 2019 consid. 7.2.1 non destiné à la publication; 6B_612/2018 du 22 août 2018 consid. 2.2).
2.3.3. Ainsi, compte tenu de la mauvaise intégration du recourant en Suisse, de l'absence de relations professionnelles ou sociales dans ce pays et des liens - notamment familiaux - conservés avec la Somalie, il n'apparaît pas que l'expulsion ordonnée pourrait placer l'intéressé dans une situation personnelle grave. La première condition cumulative permettant au juge de renoncer exceptionnellement à l'expulsion fait donc défaut. Partant, une application de l'<ref-law> ne pouvait entrer en ligne de compte. Le grief du recourant doit être rejeté.
3.
Le recours doit être rejeté dans la mesure où il est recevable. Comme il était dépourvu de chances de succès, la demande d'assistance judiciaire doit être rejetée (<ref-law>). Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>), dont le montant sera fixé en tenant compte de sa situation financière, laquelle n'apparaît pas favorable. La cause étant jugée, la demande d'effet suspensif n'a plus d'objet. Au demeurant, le recours en matière pénale interjeté contre un prononcé d'expulsion déploie de lege un effet suspensif.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'200 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 22 janvier 2020
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke