I played as him and have done alright. Only exception was constantly getting invaded by a scripting Shaco(dude was practically flying across the map and could instagib even the tankier people). I think the main thing with him isn't to go solo assassin, but work with your team to set up ganks.
I go Rhaast with him every game and play him as more of bruiser also because Rhaast looks frekking baddass. He's all dragony/demonic and has horns and armor and that super deep voice and can apparently even 1v2 Darius and Sion wheres Kayn can only 1v1 Ashe.
He already has a pretty strong kit. 2 good damage abilities and an easy way to get to/ Brave Sir Robin away enemies while healing yourself and you can even get all sexxay with him and come inside the enemy.
I haven't tried this yet but I suspect that if you can get some good CDR you'll have a pretty good burst combo. E Q or Q E the target, do an autoattack or two, Ult them. Hang out inside them violating them while waiting for your CDs, climax in them and burst out. by then E and Q should almost off CD so do that again. If the target isn't dead then, you need to learn to not focus the tank first, or berate yourself or your team for feeding them.
And yes, his early game is a bit weak and to get started you need a good leash and to be able to pull off good ganks. Also don't try and 1v1 the enemy jungler early on. If they invade, use your E and to Brave Sir Robin Away.