Hopefully you don't mind the bad joke -- but seriously, I leave in a couple of days by plane. Usually travelling is when I regress to non-paleo options. I'm wanting to have some snacks with me though (I have to avoid airline peanuts, as they are coated in a wheat starch). Obviously a granola bar is out.
The best thing I thought of was a couple of Larabars, but I'm sure there are other good options. Oh, and I'd rather it not be something messy, if possible. Thoughts?
If you plane trip is 16 hours or less you could just fast the entire time. Might want to 'practice fast' before your trip, but it's really not that bad. I did this recently for a 13 hour stretch of travel, worked pretty well, and I would have had no problem doing it for another 8 hours easily.
Then you don't have to worry about bringing food along.
For travel days/flights over 12 hours, I bring macadamia nuts. They fueled me through a 36hr travel "day" back from southeast Asia. Traveling internationally makes bringing food (especially produce or "home cooked" meats) difficult and can result in increased scrutiny and possible confiscation. The macs look benign enough, I guess.
I'm not sure if you can bring a little cooler bag but if you can, you could cook some meat or chop some vegetables or whatever and bring it along. Also stuff that doesn't really need refrigeration like cheese, hardboiled eggs, beef jerky, fruit- stuff like that.
I would advise against anything strong-smelling (please for the love of god no sardines) for the sake of the people sitting around you.
Or you could just IF. I've done that on flights that are 14 hours long. Since you're sitting down and doing pretty much nothing the whole time, it's extremely easy.
Most airlines will provide a choice for people with celiac disease: that food is often the most similar to paleo that you may find at a plane! Also some good suggestions, that you could bring yourself are hard boiled eggs, fruit, even some bacon or cheese if you have dairy. That may not be enough to satisfy you, but may help greatly if the food they serve is not acceptable!