You're absolutely correct: he can automatically have the upper hand in lanes against mages, or he can dominate games where he wins lane, but both is obviously problematic.
That said, I want both. Well, to be specific, I want to keep the anti-mage angle, and I want to keep the mad scaling, but I think it should be possible for him to win lane without transitioning smoothly into the late-game power fantasy. My thoughts:
– Just because he has an advantage against mages doesn't mean he's got to win the lane. His pre-6 gankability is a serious window of vulnerability that could be further widened by weakening the self-peel of his E. What if it only slowed people who were moving away from him, or otherwise didn't help him survive a gank? I think the tactical-level gameplay of LoL is fantastic, and I want more attention paid to the strategic level: vulnerability to ganks or lane swaps is important vulnerability.
– Another laning consideration is that he should be susceptible to the "push the wave to tower and roam" strategy, since he has trouble clearing it back. How could you change his laning such that traditional mages can clear a wave against him post-6 without opening themselves up to an all-in? Essentially, is it possible to maintain his advantage over mages in a protracted situation like laning without him having a powerful all-in? I feel like if any assassin needs a weak all-in, it's this guy. Maybe you should lower CDs, mana costs and damage numbers so he's got the same damage over time, but doesn't frontload it as well.
– You know what I loved about Ryze? Mana scaling. Now his scalings are all muddled, and there aren't enough mana items that he wants to buy since he's been told forcefully to leave Frozen Heart alone. Kassadin already has some mana scaling. I think more mana scaling could help because, outside of Seraph's and Rod of Ages, there isn't a lot to buy with mana and AP. Replace some of his AP ratios with mana ratios, which leads me to...
– Delaying the late-game fantasy. Just because he's won lane doesn't mean he's in position to be powerful in the midgame if he's put his gold into slow-burn items like RoA. What if he was forced to choose between rushing AP items for the faster power spike with a lower peak, or buying the slow-developing mana-oriented items for a weaker midgame and that lategame fantasy? Maybe the mana ratio on his ult could scale with level so that the full power of Seraph's and RoA only unlocks at 16.
So, in short, I like the anti-mage, I like the scaling, and I'm willing to sacrifice burst damage and midgame power to achieve it. How's that sound to you?