Faits: A. Par jugement du 7 février 2013, le Tribunal de police du canton de Genève a condamné X._ et C._ pour escroquerie, respectivement à une peine pécuniaire de 150 jours-amende à 30 fr. et 90 jours-amende à 30 fr., sous déduction de la détention subie avant jugement, avec sursis pendant trois ans et a mis un tiers des frais à la charge de chacun. B. Par arrêt du 4 novembre 2013, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a rejeté les appels formés par X._ et C._. En bref, il en ressort les éléments suivants. En 2005 et 2006, X._ était administrateur et actionnaire des sociétés D._ SA et E._ SA, actives, puis dormantes selon les périodes, dans le domaine de l'organisation de tournois de poker à l'étranger. En substance, il lui est reproché d'avoir engagé différentes personnes à des salaires sans commune mesure avec leurs activités réelles et ne correspondant pas aux salaires réellement perçus et d'avoir ensuite faussement annoncé divers cas d'incapacité de travail, pour lui-même, son épouse C._ ou d'autres employés, auprès des assurances pertes de gains percevant ainsi, pour lui-même ou pour ses employés, des indemnités indues. C. X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, à sa réforme en ce sens qu'il est acquitté et qu'une indemnité lui est allouée conformément à sa requête du 24 septembre 2013. Subsidiairement, il conclut à l'annulation de l'arrêt entrepris. Il requiert par ailleurs l'assistance judiciaire. Invités à déposer des observations sur le recours, A._ SA, B._ et la cour cantonale y ont renoncé, cette dernière se référant aux considérants de son arrêt. Le Ministère public a conclu à son rejet. X._ s'est déterminé sur ces écritures par courrier du 23 juin 2014, lequel a été communiqué à titre de renseignements à A._ SA, B._, la cour cantonale et au Ministère public le 26 juin 2014. 