I'm wondering what kind of boost a held item such as charcoal or nevermeltice gives. Is it like 50% damage increase?

No, it's only a 10% boost for all of those types of held items (Nevermeltice, Charcoal, etc).

Ewww I always though it was higher

In DPP they increased it to 20%, much more worth the trouble they can be to get.

Whats a good held item for my tyranitar? (Dragon Dance, Earthquake, Rockslide, Brick Break)

I'm entirely aware that this is necromancy, but I figured the best question to ask is what is the best move for Tyranitar.

Obviously, (as my thinking goes) Earthquake does a lot of damage, but it does jack squat to Flying types. So Rock Slide is a powerful move that does affect Flying types... Try finding the Rock hold item (I can't remember what it is...).

Another question, this out of curiosity. Why is this in Hoenn Region? Tyranitar is only available in FRLG as far as 3rd Gen...

Hope this helps!

AEPMT

It is hard rock From geodude/graveler

Thank you for clarifying, cytronmetagross. Obviously, as sNOwBaLL said, the type bonus from those hold items is fairly small. I personally would suggest the Shell Bell. Leftovers sort of works better for most situations, but if you're causing a lot of damage then Shell Bell is more effective.

Hope this helps!

AEPMT

Tyranitar would have to do more damage than half of its hp to exceed the Leftovers recovery (Shell Bell recovers 1/8 of the damage dealt, Leftovers recovers 1/16 of total HP). Unless you're bringing out Tyranitar late-game, when your opponent's physical walls are mostly dead and Tyranitar is free to sweep, Leftovers would be better.