The 'normal' negative sentence would be 私は肉を食べない。'I don't eat fish'. With the object marker を overridden by は this implies that not eating meat is in contrast to eating something else (for example fish). Note: When Japanese refer to meat (肉) they generally would not understand that as including fish (魚).
This contrastative は can fit in places that you might not expect. Take 生きている '(she's) alive.' vs. 生きてはいる '(she's) alive (but not well).'.
P.S. How's the Hero / Villain / Hostage example?
Very helpful :)
In your comment, you said "私は肉を食べない。'I don't eat fish'”, but obviously you meant to say 'I don't eat meat'. I also liked the hostage example! :-)