Vel'Koz main for almost two years now.
Role in a team: he's shifted to kind of a tank shredding mage due to his rework and his potential for straight true damage. Still a great pick in any team though when you need a strong source of team fight damage.
Core items: AP became much more valuable with the rework. My normal build is usually Morellonomicon>Luden's>Lucidity Boots>Deathcap>Abyssal/Zhonya's. If you need both Zhonya's and Abyssal, pick up Sorcerer's Shoes instead since you'll be over the CDR cap. In difficult lanes Rod of Ages is pretty good on him now instead of Morellonomicon, you get the same Mana and AP but trade CDR for health. In most cases I avoid Rylai's. W is the only ability that gets any real effect from it. If you need the health, grab ROA, Liandry's, or even a Banshee's Veil if you really need the defense. In some cases it can be worth a buy, but generally your gold is much better spent on something else.
Order of leveling skills: Since the rework I'm maxing R>Q>W>E. W's AP ratio nerd wasn't huge but Q is now much better for wave clear and helps with mana management if you use it correctly. W max should still be okay, I just prefer Q now.
Runes/Masteries: I usually take 12/18/0 with Merciless, Intelligence and Thunderlords. 18/12/0 with Deathfire is good sometimes into tougher lanes.
Synergy: works well with a frontline that can peel for him (Maokai, Sion, Gragas) and champs that keep the enemy team grouped together (Sejuani, Amumu)
Counterplay: Dodge the E. Really. Vel'Koz rarely kills someone without unloading his full combo, and landing the E is what sets up the ultimate. Of course, Q will slow you if it hits and make E easier to land so... dodge that too, if you can. Mobile champs like Fizz, Yasuo, Zed, Talon, etc. are really bad matchups for Vel'Koz.