Faits: A. Par jugement du 25 mars 2013, la Cour d'appel pénale du Tribunal cantonal vaudois a rejeté l'appel formé par X._ contre le jugement du 26 novembre 2012 du Tribunal de police de l'arrondissement de Lausanne le reconnaissant coupable d'injure et le condamnant à 5 jours-amende à 20 fr. le jour avec sursis pendant deux ans. Elle s'est fondée sur les principaux éléments de fait suivants. Il lui est reproché d'avoir traité Y._ de " bouffon " dans une salle de fitness après que ce dernier avait insisté pendant plusieurs minutes pour pouvoir utiliser un des appareils sur lesquels il s'entraînait et que, manifestement furieux de l'absence de réaction de X._, il s'était approché de lui pour obtenir la libération de l'appareil convoité. B. X._ forme un recours en matière pénale au Tribunal fédéral. Il conclut, sous suite de frais et dépens, principalement à la réforme du jugement attaqué en ce sens qu'il est acquitté du chef d'accusation d'injure. Subsidiairement, à sa réforme en ce sens qu'il est exempté de toute peine. Plus subsidiairement au renvoi de la cause à la Cour d'appel pénale du Tribunal cantonal vaudois pour nouvelle décision. Finalement, il demande à être libéré des frais de procédure mis à sa charge y compris l'indemnité allouée au défenseur d'office. Invitée à se déterminer, la Cour d'appel pénale a renoncé à formuler des observations. Il en va de même de Y._. Le Ministère public n'a pas répondu. 