Here's a lovely Instructable from Scoochmaroo, explaining how to make an edible (well, more edible) brain out of a watermelon -- suitable for vegan zombies.
Melon Brains (via Make)
# Slice off bottom of watermelon so it won't roll around.
# Peel green skin off of the watermelon.
# Score brainy folds in white flesh.
# With a sharp paring knife, carve channels out of melon to resemble cortical folds.