I struggle to lane against Zed as Vel'Koz

max w first and push the wave fast and back off to your tower. Zed can't match your clear speed but he needs to farm so he either needs to try to all-in you before you manage to clear the wave or he has to focus on farming too so he uses his abilities on the wave. If you can clear the wave fast enough (at some point 2x w is enough for the whole wave), you can roam to bot or top and use your ult there to get easy kills while zed is stuck mid having to farm.

As the other guy said, when zed ults you, you can use your e behind you right when zed is about to appear there so you can hit him with e+q+w and you even have time to walk away from him to gain some distance. Your burst should hurt enough to discourage him from continuing the all-in. Just remember to hold your e and not use it on minions so he can't have a window of opportunity to kill you. Also get an early hourglass.

Wait till he ults, once he does unload everything on him, takes a bit of practice to get the timing but trust me, it works wonders

Afk farm the lane. Max W first. Use Q/E to last hit.

Don't die to him, he won't snowball. He roams, you get plating.

Think about taking barrier or exhaust.

ALWAYS get no exceptions you can also take double armor runes and even resolve secondary with bone plating. refrain from using you CC ability to to poke hold it for protecting yourself. If he ulties you aim that CC ability behind you ( the opposite side your champion is facing ) timing on it might take practice.

When he ults you he will always appear behind you, save your CC for then. Don't use it for anything else.

People have already said it but rush your Seeker's and finish it first. The majority of people who have trouble against Zed (in a relatively equal skill match up) are the people who don't rush a Seeker's and don't optimize their runes.

Also, you should be using Zhonya's as soon as he appears from his ult. So he casts on you, the X appears, then Zed appears - cast right when he appears after the X because that's when he begins stacking his damage on you. His ult lasts for 3s and Zhonya's lasts for 2.5s, you will mitigate FAR more damage using Zhonya's this way, instead of using it for the pop and additionally, Zed will have no energy/cooldowns. The ult will still deal damage but you will avoid more of it this way.

You could also watch The Eggsalad or Azzazzap in action on their streams. They are both Velkoz mains (Egg is a support main though) which have faced Zed at mid on their respective channels.