Alternatives to serve with a tomato salad
halloumi or feta for cheese substitutes, especially if you can get the mint halloumi cheese.

as for ham substitute, I'd recommend toasted pita (served on top of the salad where you let the eater crush the bread themselves) or smoked salmon