In Detroit (DTW - Delta hub) there are lots of places you can get meal-sized salads(I'd still ask for dressing on the side, not on top) - typically with grilled chicken or the like on top. One of the better places was in the Guinness Pub - which had a salad with smoked salmon, egg, and horseradish among other things - but there are plenty of other places with good salad choices. Also, several other places(mostly in A terminal, not C/B) where you can get a steak with some veggies - though no promises about what the steak is cooked in. Last time through Detroit I had an early flight home connecting through Detroit so missed breakfast, so I took a grab & go chicken Caesar salad at one of the coffee shops - skipped the dressing - just greens, chicken and cheese - made a decent enough breakfast.
On the other hand, Tokyo-Narita... not such a good place for Paleo(Japan is pretty horrible for Paleo in general unless you're eating sashimi or cooking for yourself). Best I've done there is the Delta lounge, removing the bread from the little sandwiches they had. I got a lot of strange looks for doing that, and eating the meat/cheese along with some fruits/veggies. You can probably find something decent at one of the places outside, BEFORE you clear security, I'd guess.
I like to pack a little jerky/other food of my own to tide me over. But when I'm on a long, intercontinental flight I just relax a bit and chalk that up to my 20% - I still absolutely, 100% skip the bread, though.