But... Which one?

Gnar, Rek'Sai, and Azir are probably already on the list for nerfs. None of them are getting reworked, but nerfed in a later patch eventually.

Orianna has remained un-nerfed for a looooooong time so I would say she is safe for the time being.

But out of all the ones listed, Vel'koz is the most stable balance wise and not in need of nerfs / buffs or any real changes.

I really enjoy Rek'sai myself, and the nerfs were not too painful. She's still quite effective.

Fun, replayable, strong....low chances of nerfs.

Annie and Cassiopeia are both very strong top lane at the moment believe it or not...Annie never gets nerfed and Cass has already gone through her rework and fixing there of. It depends on your role you want...I'll list some options by role.

ADC - Graves and Lucian...both strong...both not getting reworked anytime soon and they're fairly stable so doubtful of nerfs. TOP - Irelia, Gnar, Jarvan IV, Rumble. Jungle - err...I dunno, sorry I stink at jungling...but I'd say Jarvan, Vi, Rengar. Support - Nami, Thresh Mid - Leblanc, Lux, Orianna

I voted for Vel'Koz. I assume this is for a Solo Queue environment.

My reasoning is

1: He is rarely banned and he can fill two roles mid and support, both of which can heavily sway a game. This makes it so you can almost always get the champion you are training with or are most comfortable on.

2: He has some okay CC in his kit. A knock up and a slow. CC wins games.

3: His ultimate is a "teamfight" ultimate. It can easily hurt a lot of players on the opposing team changing the tide of a fight. That is also what a lot of solo queue is until higher levels. There will always be sloppy teamfights, no matter what. It's unavoidable. Players don't understand how to stall or not engage. So you need to be able to be there to turn the tide of that fight so that you're team can win and focus on objectives which will ultimately win you the game.

4: A decent amount of his damage is true damage. This means that for the most part you won't have to worry too much about tanks. You will more than likely be able to just melt people with your passive. Your damage will almost always be effective.

Most of your requirements are fairly player dependent. Replay-ability depends on if you enjoy the champion. Reliability is if you can consistently play the champion well. Fun is if you find it fun, which I don't know if you will because I don't know you.

Power is subjective and depends on the current game balance. As long as you can play a champion well and heavily influence your games in a positive way I'd say that is "powerful". Not likely to get reworked, I guess you're safe there, he's fairly new and he isn't considered severely overpowered or under-powered.

If for some reason you decide not Vel'Koz, my next recommendation would be Orianna for somewhat similar reasons. She is just a little harder to play and get used to because you have to keep track of the ball to use her effectively and the speed of some of your spells is dependent on the location of the ball. If the ball is far away and you need instant damage right in front of you to finish someone off, you're out of luck because it has a travel time, just something to think about though, she's still very effective.

Note: Both of these champions are ranged. You will find it somewhat easier to influence games because of that. You can do your job with little risk.

Hope I helped :)

Also!

Feelin' lucky. The new champ rotation includes Azir and Gnar! I get to try them out =D

Maybe the first time I've said this non-sarcastically in 4 years: Thank you Riot

Bumperino