Faits : A. Par jugement du 19 août 2015, le Tribunal de police de la République et canton de Genève a reconnu X._ coupable de menaces (art. 180 al. 1 CP) et l'a condamné à une peine pécuniaire de 40 jours-amende, a fixé le montant du jour-amende à 30 fr., et mis le condamné au bénéfice du sursis avec un délai d'épreuve de deux ans, le tout avec suite de frais et dépens. B. Statuant sur appel de X._, la Chambre pénale d'appel et de révision de la Cour de justice de la République et canton de Genève l'a rejeté et a confirmé la décision de première instance. En bref, l'arrêt se fonde sur les faits suivants. Par téléphone, le 22 novembre 2013, X._ a menacé de mort A._, gestionnaire de dossiers auprès de l'Office cantonal des assurances sociales (ci-après: OCAS), après qu'une demande de prestations AI lui avait été refusée. En l'absence de A._, sa collaboratrice B._ avait répondu à l'appel. Lors de la conversation téléphonique, X._ avait notamment déclaré, s'agissant du médecin en charge d'une expertise sur sa personne, " Vous savez que le Dr C._ est décédé, j'ai eu un contact avec lui et je l'ai tapé ". Avant de raccrocher, il avait encore dit " Madame aaa, vous êtes morte ". B._ avait retranscrit ces propos dans une note interne qu'elle avait remise à A._, laquelle avait été effrayée. C. X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut à l'octroi de l'assistance judiciaire, à l'annulation de l'arrêt cantonal et au prononcé de l'acquittement avec suite de frais et dépens. Subsidiairement, il requiert le renvoi de la cause à la cour cantonale, respectivement au tribunal de première instance, pour nouveau jugement.