Definitely homemade granola or even granola bars!

http://www.coffeefoodies.com/2012/05/19/recipe-diy-holy-crap/

Note to link above - Personally... I think its the best added to yogurt.

Making your own "bisquick" or muffin mix is really easy. If you're not adverse to using either dehydrated milk/egg/oils or substitutions (like ground flax for egg), you could even make them a "just add water" mix.

A few examples (caveat: I have not tried any of these myself!)
bisquick: http://www.diynatural.com/homemade-baking-mix-recipe/
muffin mix: http://www.tasteofhome.com/Recipes/Homemade-Muffin-Mix

How about homemade English muffins! http://www.foodnfocus.com/homemade-english-muffins/

Smitten Kitchen had a to die for recipe of granola covered nuts, great for breakfast on the go or snack. TO DIE FOR. http://smittenkitchen.com/blog/2012/11/granola-crusted-nuts/
I would also think about doing homemade energy/breakfast bars (tons of recipes on this site). And I doubt I am the only one who is a fan of cookies for breakfast...what if you did something like a healthier oatmeal cookie or a savory shortbread? Because cookies definitely travel well.

What to mail for breakfast? How long do you expect the package to be in transit? If more than a few days (anything other than priority in the USA) then go with the granola and energy bar ideas above. Dried fruits, biscotti, coffee or tea are good travelers as well.

For short trips, the cake in a jar idea is fine as long as you use the jar as a baking/mailing container, not a long-term storage container. Rather than cake, though, I'd go with coffee cake or muffins/quick breads. Leave the lid off until the baked good is cooled to avoid that botulism risk mentioned. Use a recipe that is high in fat to keep the treat moist and fresh-tasting. Anything you would store at room temperature at home is fine.

You can't go wrong with granola or homemade fruit/nut bars. You might want to check out these recipes:

Http://www.bitesforbabies.com/gluten-free-pumpkin-coconut-granola/

Http://www.bitesforbabies.com/healthy-coconut-carob-puffed-rice-bars/

I have a super healthy and easy hot quinoa and steel-cut oat cereal that I just delivered to my in-laws. I packed all of the dry ingredients into a jam jar and all they needed to do was add 4 cups of water when they wanted to make it. I also put the link to my blog post on the back of the back of the jar so they knew how to make it. It's the easiest cereal to make because you make it the night before ,just bring cereal to boil, cover and let sit overnight and just re-heat it in the morning.
Here's the link: http://www.marinmamacooks.com/2013/02/hot-quinoa-and-oat-cereal-with-goji-berries/

Never mind what to mail for breakfast- you are a SUPER awesome friend! :o)

If you expect the package to travel more than a few days, forget muffins or little cakes. Make some big cake wich will keep moist longer - ginger bred and altrii. And put a jar or a tube of something to spread over, as nutella or speculoos spread.

Are you sending breakfasts because they can't cook for themselves? Do they have access to a pantry or a microwave, or do they need to eat them right out of the box?

Our grocer has small cans of evaporated milk (or you can get aseptically packed milk boxes) which, if they didn't have milk but had access to a microwave, I would include with dry premixed homemade hot cereals in jars, like oatmeal with some of these dry mix-ins http://www.thekitchn.com/make-deluxe-oatmeal-10-awesome-mix-ins-168535

Otherwise, why not bake? Muffins and home-canned jam, scones (sometimes you can find canned Devon cream at the grocer) or quickbreads, etc.

Jams, cheeses, coffee, tea, dried berries, some pastries shipped overnight?

What a funny coincidence, that is been an idea of mine that's never been put to practice, but, anytime I think of the possibilities it ends up in:
1) nice basket
2) granola
3) small jars of apricot, strawberry and orange jams.
4) pancake mix, or waffle mix. You can substitute for biscuits or English muffins.
5) small jars of something spicy, salsa or chutney to make simple cheese omelette stand out. For the savory breakfast types.
For the breakfast to be done the recipient should provide with eggs, milk and coffee.
Hope you do make it and then tell me about it so I can pull of the courage to do it.

Sorry for getting back so late, been burried under work lately - thats also the reason i could not visit someone for a promised breakfast and want to make them a nice surprise.

A full kitchen is available at the recipient, as well as all the shops to get own breakfast. I just want to make it as a nice surprise, no actual need to send food there.
The package might be on the road for a couple days, worst case maybe a week or so if its getting picked up later (since none expects it to arrive).

I'm a bit shocked to read about the cake in the jar issue. Never would have thought about that and since there is even a shop in town selling and sending them i was quite confident they are safe. But maybe they have them cool down before also.

Something everyone seems to suggest is something granola/oatmeal/cereal related. Unfortunately i'm not really a expert in this, usually sticking with my store bought mix, but ill check out the recipes you put, some seem quite nice.
At the worst case i guess ill just order a few "special mixes" online, since they come already ready packed for transport - its amazing what one can order on the internet these days, even to-order mixed granola/oatmeal/cereal mix (mymuesli.com).

I quite like the basket idea - not really sure why i did not think of that myself. With eastern coming that should be easy to find one for shipping as well. And empty space can be filled up nicely with some chocolate rabbits :-)

For Valentines day, I sent my son a care package of breakfast goodies to his dorm from Nuts.com which was a huge hit. They are a fantastic resource, by the way, but you could do something similar DIY : oranges, dried cherry granola, boxes of vanilla almond milk, box of chai mix. Decorate the box with stickers or your own graffiti.
You're a good egg, BenjaminH!