I need something not too messy and that doesn't take up too much space in a carry on.
Anything you would do when sitting in a chair at home, as long as it is not messy and does not involve sharps and long blunt objects.
I think drawing, writing (by hand,) crochet (medium sized hook, like a 2mm to a 5 mm) (sorry, I do not know the American/UK equivalents)
Tatting and knitting on circular needles and other yarn crafts that do not need tools or much space. Origami, specially when you are willing to share out well worked out results between kids (and adults) who are on the plane.
I would do knotwork, as I would not have to use tools and the scale I work would make it suitable. Friendship bracelets might be an option.
Other knot options you find on my website (beginners ideas), or here (animals), which has small objects for which you do not need much space (on both sites hit the home button at the bottom of the page to get the full site).
Pre-cut and finished off lengths of string would be best but I have been able to bring a tiny folding knife with a very small set of scissors on board.
I would not work with beads or other crafts with small, easily dropped items which might run away in the plane. As it is very likely that you will not be able to retrieve them from underneath other seats. Nor would I bring any tools I would hate to lose. Security does allow many craft tools as long as not sharp, but they do not allow all.
You can bring glue in small amounts (in your liquids bag) but working with it to finish of ends of string might be a bit too fiddly.
And remember, if you can not do it, you can read about it. This might be the time to read that craft book you have never had time to really read or download a series of videos (youtube or alike) and study them while you are in the air.
I do knotting and weaving and have picked up a lot of tips from Willeke, who mentions it briefly in her answer. In my case I take two strands of mil spec 550 paracord, and some European style beads and build up something like this...
The split rings and bolt snaps are readily available from hobby shops or the net. The Euro beads are similarly available, but sometimes I will use a lampwork provider.
I keep all the stuff for one project in a 'zip lock' baggie and might have one or two such baggies with me depending upon voyage length.
Willeke has lots of 'how to' pages on the net and is usually in the chat room during European evening hours.
I also carry a Delorme Communicator which has an iPad interface and almost always provides usefulness as well as diversion.