This might be true in the US, but in London privately-owned sandwich shops are VERY common, there's like 6 of them within 30 seconds walk of my office. They'll typically serve mainly sandwich and wraps (made to order), or alternatively potato, pasta or rice-based meals.
There are some places that specialise in salad/veg rather than sandwiches, but they tend to be vegetarian with the only calories coming from cous cous or potato.
Interesting. However, if they serve sandwiches, perhaps they also have "grilled chicken cutlet sandwich". If they do, no harm in just asking for the chicken and whatever other toppings you like (cheese, lettuce, tomato, etc.)
There are some places that specialise in salad/veg rather than sandwiches, but they tend to be vegetarian with the only calories coming from cous cous or potato.
I'll have a look around though.