Just played a couple of dominion games and he has a definite learning curve. His spells are hard to hit at first, especially his e, but their not atrouciously hard to hit. His w obviously isn't reliable harass, but it's got good waveclearing, so I imagine Vel'koz will mostly farm with that.
His Q can get off a lot of tricky hit, using basic geometrics. To bad all your other spells are better to max.
His full e-w-w-r (q) combo can easily kill somebody. His spells, aside from his ult, don't have big tells.
His itembuilds are kind of meh, you want defense, but Zhonyas is suboptimal, Abyssal meh, Rhylais redundant for 2 out of 4 of your spells ...
I do think it's to early to tell wheter he's op or not. His damage + range might put him in some teamcomp or his Q spamability might be to much.
I've played 2 games of him so far (as a midlaner), and from what I can tell, most matchups are skill matchups, with the skill of Vel'koz being more important than the skill of the opposing laner. He's superfun, but I'm not sure how healthy he is for the game, especially higher tier play, until I've played as/vs him more times. My second game was MUCH better than my first, but we still lost due to having a legendary (toplane) Zed and Ezreal to deal with (I probably should have roamed more).
If he can aim his Q, he can hit you from practically any position in lane. It moves really fast, so it's tricky to dodge it after the split. Twice I even managed to stand in front of the minions, and shoot it BETWEEN the melee and ranged to hit the enemy laner. Most of the Q's I missed (which were quite a lot) were due to a mistake on my end rather than the laner dodging it. It's his most fun ability IMO. It's tricky, but rewarding to hit, and playing around with the geometry is really fun. It can also be used to check bushes if it breaks early, or if one of the splits ends abruptly. His W's waveclear is ridiculous, and can simultaneously poke the enemy laner if they're standing in their wave, but the second half is easily dodged. Hitting an E directly after W pretty much guarantee's his passive proc, which is a LOT of damage. E is probably his worst ability, but his only form of hard cc. Compared to Nami's bubble (which is similar), it's harder to hit, does less damage, has a longer cooldown, and has less cc attached. It's a one point wonder and is pretty much only used for self peel or proccing your passive. His ult is super powerful, but it countered hard by champs with a lot of mobility. If you wait to use it in a teamfight it can single handedly win the fight. I arrived a little late to a fight and we were 3v5 left over. I channeled my ult on about 4 of them, and killed one straight out, but the other was saved by a Kayle ult. With a trickshot Q I picked up a double kill and we ended the teamfight 2 for 2, even though we were outnumbered.
His lack of mobility is a HUGE weakness though, so I actually think he's pretty balanced. Assassins will wreck him late (maybe not in lane) unless he's really good, and I think Protect The Vel'Koz teams will be really viable. So far, I think he's pretty balanced.