Annie is amazing for a beginner. Q for last hitting is phenomenal and you don't have to deal with aiming. However, you will find yourself out ranged by most opponents meaning you will eat quite a bit of damage and most champions can win trades against her just fine unless you can close the gap with flash. New players don't have flash, and even when you do, it's a long cooldown.
Velkoz doesn't have that issue. His skill shots travel fast, other than Q, and are some of the easiest in the game to land. He does consistently high damage that while not as easy to land as Annies, come from far away and is among the easiest of the skillshot mages to apply.
My point is, Velkoz is not hard like some people seem to think. I have been playing him off and on since his release and have lvl 5 mastery on him and Annie on multiple accounts. When Annie has a favorable matchup, she is oppressive as hell. When she doesnt, she is a boat anchor tied around her team that they can occasional get a lucky throw onto the enemy with a flash Tibers. Velkoz has far fewer bad matchups and they are less harmful to him thanks to safe range farming.
You can't go wrong putting either of those champions into the hand of a beginner.