I'm also a bit skeptical about mailing food. Once my cousin posted me a letter with a piece of crackers with cream cheese, and it never arrived.
But when I sent her crackers inside a plastic envelope, it did... so...
Ok, here are some stuff that are don't know if are originally Brazilian, but are common around here.
Pé-de-moleque (something like "kid's foot")
It's a sweet made of peanuts. Nice.
Rapadura (something like "hard to sweep")
Don't know what it's made off. But it's hard and tastes good. Usually home-made, never seen one of those for buying.
GoiabadaA sweet thing made of goaba. People usually eat it with cheese, but I don't like cheese.
PaçocaAlso made of peanuts. Very strong sweet taste.
CocadaMade of coconut. Very nice.
I'll post when I remember more.