Faits: A. Par jugement du 30 novembre 2005, le Tribunal de police du district de Boudry (ci-après: le Tribunal de police) a condamné X._ à sept jours d'emprisonnement avec sursis pendant deux ans et à 500 fr. d'amende pour lésions corporelles simples et diverses infractions à la Loi fédérale sur la prévoyance professionnelle vieillesse, survivants et invalidité ainsi qu'à la Loi fédérale sur le séjour et l'établissement des étrangers. Le Tribunal de police a notamment retenu les faits suivants: Le 13 novembre 2004, une dispute est survenue entre deux employés du restaurant exploité par X._. Celui-ci est intervenu et a demandé à Y._, qui était impliqué dans la dispute, de s'expliquer. X._ a alors injurié Y._, qui était occupé à couper du pain et tenait de ce fait un couteau. Il lui a donné une "très violente baffe", provoquant un saignement à la lèvre. Y._ a dit à son patron qu'il trouvait son attitude inadmissible et, comme il tenait un couteau à la main, lui a déconseillé de l'approcher à nouveau; il ne s'agissait pas d'une menace, mais uniquement de l'expression de la volonté de se défendre contre une nouvelle attaque. Très en colère, il a ensuite jeté le couteau sur la table et a déclaré qu'il quittait sa place de travail avec effet immédiat. X._ l'a empêché de sortir par la terrasse, de peur que ses clients ne voient son employé saigner de la bouche. Alors que Y._ s'apprêtait à sortir par un autre endroit, X._ s'est précipité sur lui et l'a saisi violemment par les cheveux, en lui passant un bras autour du cou. Il l'a traîné à travers la salle du personnel, puis lui a arraché une grosse poignée de cheveux. Y._, a porté plainte contre son patron pour lésions corporelles, voies de fait et injure. Quant à X._, il a déposé plainte contre son employé pour menaces. Un examen médical effectué le 15 novembre 2004 a révélé que Y._ présentait une rougeur du cuir chevelu au niveau pariéto-occipital, avec beaucoup de cheveux arrachés, de même qu'une plaie de 0,5 cm à la face intérieure de la lèvre inférieure, ainsi qu'une tuméfaction. Les faits retenus par le Tribunal de police correspondent à la version donnée par Y._. Confronté à une version différente de X._, le premier juge l'a écartée. Il a notamment relevé des divergences importantes dans les témoignages favorables à X._ et a acquis la conviction que seule la version de Y._ correspondait à la réalité. B. X._ a recouru contre ce jugement auprès de la Cour de cassation pénale du Tribunal cantonal du canton de Neuchâtel (ci-après: le Tribunal cantonal), qui l'a confirmé par arrêt du 14 mars 2006. En substance, le Tribunal cantonal a considéré que le Tribunal de police n'avait pas fait preuve d'arbitraire en privilégiant la version de Y._. C. Agissant par la voie du recours de droit public, X._ demande au Tribunal fédéral d'annuler cet arrêt. Il invoque les art. 9 Cst. et 6 par. 2 CEDH pour se plaindre d'arbitraire dans l'appréciation des preuves et d'une violation du principe de la présomption d'innocence. Il se plaint également du fait qu'il n'a pas pu se prévaloir de l'état de légitime défense au sens de l'art. 33 CP. Y._ s'est déterminé; il conclut au rejet du recours et requiert l'assistance judiciaire gratuite. Le Tribunal cantonal et le Ministère public du canton de Neuchâtel ont renoncé à formuler des observations.