Faits :
A.
Par jugement du 15 décembre 2014, le Tribunal de police de la République et canton de Genève a acquitté X._ de la prévention de menaces. Il l'a déclaré coupable d'injures et d'infraction par négligence à l'art. 33 al. 1 let. a et al. 2 de la loi fédérale sur les armes, les accessoires d'armes et les munitions (Loi sur les armes, LArm; RS 514.54). Il l'a condamné à 10 jours-amende à 35 fr. le jour avec sursis durant trois ans et à une amende de 300 francs. Il l'a également condamné à verser à A._ une indemnité de participation à ses dépens de 1'620 fr. et à payer les frais de procédure.
B.
Par jugement du 1 er juillet 2015, la Chambre pénale d'appel et de révision de la Cour de justice de la République et canton de Genève a rejeté l'appel de X._ et l'a condamné à payer une indemnité pour frais de défense de 2'241 fr. à A._ et les frais de justice.
La cour cantonale a retenu les faits suivants.
X._ a travaillé en qualité d'attaché de l'Ambassade de Suisse à W._. A cette époque, il a acquis une arme pour laquelle les autorités du pays lui ont accordé un port d'arme dès 2002. A son retour en Suisse en 2003, il a emmené cette arme avec lui, sans en aviser l'autorité compétente et sans solliciter d'autorisation. Cette arme a été saisie à son domicile genevois par la police en octobre 2013.
Dans plusieurs messages téléphoniques envoyés à A._ en septembre et octobre 2013, époque où leur relation amoureuse prenait fin, X._ a traité celle-ci de " putain ", de " rat " et de " merde ". En procédure, il a admis avoir tenu ces propos injurieux en réponse aux injures proférées par A._.
En avril 2014, X._ a été embauché en tant que vice-ambassadeur à V._. Il a dû quitter ce poste à fin août 2014 en raison de la procédure pénale dirigée contre lui.
C.
X._ interjette un recours en matière pénale au Tribunal fédéral contre le jugement du 1er juillet 2015. Il conclut, avec suite de frais et dépens, principalement à son acquittement pour infraction à la LArm et à son exemption de toute peine en rapport avec la condamnation pour injures en application des art. 52 et 54 CP. Il demande aussi l'annulation de sa condamnation à verser des indemnités de dépens à A._. Subsidiairement, il requiert l'annulation du jugement et le renvoi de la cause à la cour cantonale. A._ conclut au rejet du recours.
X._ présente une demande d'assistance judiciaire.

Considérant en droit :
1.
La cour cantonale, se fondant sur les déclarations du recourant, a retenu que celui-ci avait possédé illégalement une arme à son domicile après l'avoir importée sans avoir obtenu l'autorisation nécessaire. Elle a considéré que cette arme, acquise légalement à W._, ne dispensait pas le recourant de demander une autorisation pour l'importer en Suisse. Elle a aussi admis que le recourant avait agi par négligence.
1.1. Le recourant conteste l'appréciation de la cour cantonale. Il estime que les conditions d'application de l'art. 33 al. 1 let. a LArm ne sont pas données. Il considère que son arme a été acquise légalement à W._ et qu'en conséquence l'art. 12 LArm l'autoriserait à la posséder. De plus, il affirme ne pas avoir besoin du permis d'acquisition d'arme exigé par l'art. 8 LArm car cette disposition légale, entrée en vigueur le 12 décembre 2008, n'aurait pas d'effet rétroactif et ne s'appliquerait donc qu'aux cessions d'armes postérieures à cette date.
1.2. L'art. 33 LArm punit d'une peine privative de liberté de trois ans au plus ou d'une peine pécuniaire quiconque, intentionnellement et sans droit, notamment acquiert ou possède des armes (al. 1 let. a). Si l'auteur agit par négligence, la peine est une amende (al. 2).
L'art. 12 LArm dispose que toute personne ayant acquis légalement une arme, un élément essentiel d'arme, un composant d'arme spécialement conçu ou un accessoire d'arme est autorisé à posséder l'objet ainsi acquis. Cette disposition légale subordonne l'autorisation de posséder une arme ou un élément essentiel d'arme au fait que l'engin ait été acquis en toute légalité (Message du 1er octobre 2004 relatif à l'approbation des accords bilatéraux entre la Suisse et l'Union européenne, y compris les actes législatifs relatifs à la transposition des accords [accords bilatéraux II], FF 2004 5593 p. 5893).
1.3. Le recourant a importé l'arme en Suisse en 2003, avant l'entrée en vigueur de la modification de la loi générée par les accords bilatéraux II. A l'époque de l'importation, l'ancienne LArm prévoyait qu'une arme telle que celle possédée par le recourant, pouvait être acquise auprès d'un commerçant moyennant l'obtention d'un permis d'acquisition d'armes (art. 8 al. 1 aLArm) ou auprès d'un particulier moyennant signature d'un contrat écrit (art. 9 al. 1 aLArm en rapport avec l'art. 11 aLArm). Ces dispositions règlementaient l'acquisition des armes en Suisse par des ressortissants suisses, domiciliés en Suisse ou à l'étranger (art. 8 al. 3 aLArm), ou par des étrangers titulaires d'un permis d'établissement. Le recourant ne peut pas se prévaloir de ces dispositions dans la mesure où il n'a pas acquis l'arme en Suisse. L'art. 25 al. 1 aLArm réglait la question de l'importation d'armes à titre non professionnel et précisait que toute personne qui importait des armes, des éléments essentiels d'armes, des munitions ou des éléments de munitions devait être titulaire d'une autorisation.
Il résulte de ces dispositions légales que le recourant ne pouvait importer son arme, même légalement acquise à W._, que moyennant une autorisation au sens de l'art. 25 al. 1 aLArm. Il était conscient de cette absence d'autorisation et du fait qu'il n'était pas en règle sur ce point, comme cela ressort de ses déclarations, selon lesquelles il admettait son manquement. Ainsi, au regard du droit suisse en vigueur avant la modification de la loi générée par les accords bilatéraux II, le recourant ne pouvait pas être considéré comme une personne ayant acquis légalement une arme en Suisse. Il ne peut donc pas se prévaloir de l'art. 12 LArm pour justifier la possession.
L'argumentation du recourant selon laquelle l'autorisation exigée par l'art. 8 LArm ne serait pas nécessaire car cette disposition légale n'aurait pas d'effet rétroactif et ne s'appliquerait qu'aux cessions d'armes postérieures au 12 décembre 2008 (date d'entrée en vigueur de la loi modifiée) est exacte. La jurisprudence a précisé que les armes nécessitant une autorisation et acquises valablement en conformité de l'ancien droit, peuvent continuer d'être possédées selon le nouveau droit (<ref-ruling> consid. 2.4.4 p. 137).
En l'espèce, il n'est pas reproché au recourant de ne pas avoir demandé une autorisation en application de l'art. 8 LArm et la dispense de demander une nouvelle autorisation n'est d'aucune utilité au recourant, car il ne détenait pas l'arme de façon régulière selon l'ancien droit, comme cela est exigé par la jurisprudence.
La cour cantonale pouvait dès lors, sans violer le droit fédéral, retenir que les conditions d'application de l'art. 33 al. 1 let. a et al. 2 LArm étaient données et ainsi condamner le recourant pour les trois dernières années de possession non atteintes par la prescription (art. 97 al. 3 et 109 CP).
2.
La cour cantonale a confirmé la condamnation du recourant pour injures et a refusé de l'exempter de toute peine en application des art. 177 al. 3, 52 et 54 CP. Elle a estimé que le recourant avait proféré des injures graves de nature à porter sérieusement atteinte à l'honneur de la victime et que ces injures n'apparaissaient pas négligeables par rapport à d'autres actes tombant sous le coup de l'art. 177 al. 1 CP. S'agissant de l'atteinte subie par le recourant à la suite de ses actes, la cour cantonale a retenu qu'il avait effectivement perdu son emploi en raison de la procédure pénale dirigée contre lui mais a estimé que les conséquences, même importantes, d'une telle procédure sur la situation professionnelle de l'auteur apparaissaient comme des éléments indirects. Ainsi, elle a admis qu'une mise en balance de la faute commise et des conséquences de l'acte ne rendait pas le prononcé d'une peine inapproprié ou choquant le sentiment de justice. De plus, elle a considéré que le recourant n'avait pas proféré ces injures en réponse à d'autres injures émanant de la victime.
2.1. Le recourant ne conteste plus, devant le Tribunal fédéral, l'absence d'application de l'art. 177 al. 3 CP, mais invoque une violation des art. 52 et 54 CP. Il demande à être exempté de toute peine pour l'infraction d'injures, car il estime que l'Etat n'a pas d'intérêt à punir les injures, infraction uniquement poursuivie sur plainte, alors que l'intimée elle-même n'a pas daigné soutenir les allégations graves qu'elle avait formulées. De plus, il considère qu'il a déjà été suffisamment puni en raison de l'ouverture de l'action publique eu égard à la perte de considération sociale et de son emploi, dont il affirme qu'elle est en relation de connexité avec la présente procédure pénale.
2.2. L'art. 52 CP prévoit que, si la culpabilité de l'auteur et les conséquences de son acte sont peu importantes, l'autorité compétente peut entre autre l'exempter de toute peine. L'importance de la culpabilité et celle du résultat dans le cas particulier doivent être évalués par comparaison avec celle de la culpabilité et celle du résultat dans les cas typiques de faits punissables revêtant la même qualification (<ref-ruling> consid. 5.3.3 p. 135 s.).
En l'espèce, les conditions de l'art. 52 CP ne sont pas données. En effet, la culpabilité du recourant n'est pas minime. Il a utilisé, à réitérées reprises, des termes très déshonorants à l'égard de l'intimée. L'atteinte à l'honneur de la victime ne saurait être considérée comme étant de peu d'importance au regard des termes utilisés, lesquels constituent typiquement des injures.
2.3. L'art. 54 CP, qui reprend pour l'essentiel l'art. 66 bis aCP, dispose que si l'auteur de l'infraction a été directement atteint par les conséquences de son acte au point qu'une peine serait inappropriée, l'autorité compétente renonce à le poursuivre, à le renvoyer devant le juge ou à lui infliger une peine. Une exemption de peine se justifie lorsque l'auteur paraît déjà suffisamment puni et que la fonction compensatrice de la peine est déjà réalisée (<ref-ruling> consid. 2.3 p. 108).
En l'espèce, le recourant demande l'exemption de toute peine pour l'infraction d'injures estimant que c'est en raison de celle-ci que son contrat de travail avec la Confédération suisse a été résilié, ce qui lui aurait causé un préjudice irréparable et important. Cette allégation est déjà démentie par le recourant lui-même, qui, dans son recours, précise : " le licenciement est intervenu en raison des infractions poursuivies pour lesquelles le recourant bénéficie d'acquittements, soit les menaces et les lésions corporelles ". Dans de telles circonstances, les doutes émis par la cour cantonale concernant la connexité entre les injures et le licenciement peuvent être justifiés. De plus, le Département de la défense, de la protection de la population et des sports a informé le Département fédéral des affaires étrangères (ci-après : DFAE) qu'une instruction pénale à l'encontre du recourant pour menaces et infraction à la LArm, nécessitait des investigations complémentaires sur la situation du recourant et qu'en attendant un jugement définitif au pénal, il suspendait la poursuite de son examen de la sécurité (pièce 2, lettre du 30 juin 2014). Or, avant même que le Tribunal de police n'ait prononcé son jugement, qui date du 15 décembre 2014, la relation de travail liant le recourant au DFAE avait déjà été résiliée pour le 28 août 2014, sans qu'il soit possible de dire sur la base de quels faits. Dans ces conditions, même s'il fallait admettre un lien direct entre la poursuite pénale et la cessation des rapports de travail, le recourant n'a pas établi ou offert d'établir que celle-ci était liée à la condamnation pour injures.
En conséquence, les conditions d'application de l'art. 54 CP ne sont pas réalisées.
3.
La cour cantonale a rejeté l'appel du recourant, confirmant ainsi sa condamnation en première instance à verser une indemnité de procédure de 1'620 fr. à l'intimée. De plus, elle l'a condamné à verser une indemnité à celle-ci pour la procédure d'appel de 2'241 fr., qui comprenait 900 fr., représentant trois heures de comparution à l'audience de première instance, montant non facturé par l'intimée et non pris en compte par le Tribunal de police.
3.1. Le recourant nie le droit de la partie plaignante à une quelconque indemnité en application de l'art. 433 CPP. Il conteste le caractère nécessaire des démarches entreprises par l'intimée dans le cadre de la procédure. Selon lui, l'intervention d'un avocat n'était pas justifiée. Il estime que la mandataire de l'intimée serait intervenue pour la première fois devant le Tribunal de police, alors que l'infraction d'injures était admise. L'infraction à la LArm ne pouvait pas justifier l'intervention de l'intimée, faute d'intérêt, le bien juridiquement protégé étant la sécurité. Pour les infractions de menaces et lésions corporelles, l'intimée n'a pas droit à une indemnité, le recourant ayant été acquitté. Enfin, les injures ne justifieraient pas à elles seules l'intervention d'un avocat.
3.2. Aux termes de l'art. 433 CPP, la partie plaignante peut demander au prévenu une juste indemnité pour les dépenses obligatoires occasionnées par la procédure si elle obtient gain de cause (let. a). La partie plaignante adresse ses prétentions à l'autorité pénale et doit les chiffrer et les justifier (al. 2).
La partie plaignante obtient gain de cause au sens de l'art. 433 al. 1 CPP si les prétentions civiles sont admises et/ou lorsque le prévenu est condamné. Dans ce dernier cas, la partie plaignante peut être indemnisée pour les frais de défense privée en relation avec la plainte pénale (<ref-ruling> consid. 4.1 et 4.3 p. 107 s).
La juste indemnité, notion qui laisse un large pouvoir d'appréciation au juge, couvre les dépenses et les frais nécessaires pour faire valoir le point de vue de la partie plaignante dans la procédure pénale. Il s'agit en premier lieu des frais d'avocat de la partie plaignante (arrêts 6B_965/2013 du 3 décembre 2013 consid. 3.1.1; 6B_159/2012 du 22 juin 2012 consid. 2.3). En particulier, les démarches doivent apparaître nécessaires et adéquates pour la défense raisonnable du point de vue de la partie plaignante (arrêt 6B_159/2012 du 22 juin 2012 consid. 2.3).
L'opposition à une ordonnance pénale a pour conséquence, lorsqu'elle est maintenue par le Ministère public, un renvoi de la cause devant le tribunal de première instance, l'ordonnance pénale tenant alors lieu d'acte d'accusation (cf. art. 356 al. 1 CPP). En l'occurrence, le recourant a formé opposition à l'ordonnance pénale du Ministère public rendue le 20 novembre 2013, le condamnant notamment pour menaces et injures. Dans ces circonstances, l'intimée avait tout intérêt à se faire représenter à l'audience de première instance pour demander la poursuite et la condamnation du recourant (cf. art. 119 al. 2 let. a CPP). Dans cette mesure, les frais de défense étaient nécessaires à l'intimée (cf. arrêt 6B_495/2014 du 6 octobre 2014 consid. 2.4).
Il y a dès lors lieu d'admettre que c'est à juste titre que la cour cantonale a reconnu le droit de l'intimée à une indemnité de dépens pénaux.
3.3. La cour cantonale a fixé l'indemnité due en appel par le recourant à l'intimée. Pour ce faire, elle s'est fondée sur la note d'honoraires présentée par la mandataire de l'intimée, qui prenait en compte trois heures de comparution à l'audience devant le Tribunal de police auxquelles s'ajoutaient 3,55 heures pour l'activité fournie en seconde instance, à savoir 2'075 fr. en tout et 3% de frais forfaitaires. La cour cantonale a refusé ces derniers, faute de justification. Ainsi, elle a alloué une indemnité de 2'241 fr., représentant 6,55 heures à 300 fr. et la TVA par 166 francs.
Le recourant critique le montant de l'indemnité et semble s'en prendre à l'augmentation de 900 fr. de l'indemnité à verser à l'intimée en rapport avec la procédure en première instance.
3.3.1. D'après l'art. 391 al. 2 CPP, la juridiction d'appel ne peut modifier une décision au détriment du prévenu ou du condamné si le recours a été interjeté uniquement en leur faveur (1 ère phrase).
3.3.2. En condamnant le recourant au paiement d'un montant supérieur à celui arrêté en première instance au titre des frais de défense de l'intimée en première instance, la cour cantonale a modifié la décision entreprise au détriment du recourant. La refixation de l'indemnité de première instance allouée à l'intimée, alors que seul le recourant a formé appel, contrevient à l'interdiction de la reformatio in pejus.
Ainsi, le recours doit être admis sur ce point. Le recourant ne contestant pas le tarif horaire du mandataire de l'intimée, ni le nombre d'heures de travail admis pour la procédure de seconde instance, il y a lieu de réformer le jugement cantonal en ce sens que l'indemnité de dépens pénaux due à l'intimée est réduite à 1'175 fr. plus 8% de TVA, à savoir 1'269 fr. au total.
3.4. Au vu de l'issue de la procédure, le recourant n'obtient gain de cause que sur un point accessoire. S'agissant d'une réduction de l'indemnité de dépens pénaux à l'intimée allouée par la cour cantonale, il n'y a pas lieu de lui renvoyer la cause afin qu'elle examine la question des frais et dépens relatifs à cette instance.
4.
Le recourant n'obtient gain de cause que sur un point accessoire. Il peut prétendre à des dépens réduits (art. 68 al. 1 LTF). La demande d'assistance judiciaire devient sans objet dans cette mesure (art. 64 al. 2 LTF). Les conclusions du recourant étant, pour le surplus, dénuées de chance de succès, la demande d'assistance judiciaire est rejetée (art. 64 al. 1 LTF). Le recourant supporte des frais réduits fixés en tenant compte de sa situation économique (art. 65 al. 2 et 66 al. 1 LTF). L'intimée, invitée à se déterminer sur la seule question des indemnités au sens de l'art. 433 CPP, peut prétendre à des dépens réduits, dans la mesure où elle obtient partiellement gain de cause.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis. Le jugement entrepris est réformé en ce sens que le recourant est condamné à payer à l'intimée la somme de 1'269 fr., TVA comprise, à titre d'indemnité pour ses frais de défense dans la procédure d'appel.
2.
Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recourant.
3.
L'Etat de Genève versera en mains du conseil du recourant la somme de 500 fr. à titre de dépens.
4.
La demande d'assistance judiciaire est rejetée dans la mesure où elle n'est pas sans objet.
5.
Le recourant versera à l'intimée la somme de 1'000 fr. à titre de dépens réduits.
6.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 1 er novembre 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke