Karthus, Veigar, Azir, Caitlyn all say hello.
Ok here is how you beat a hiemer, coming from a person who plays heimer.
First... You must never let a heimer be given enough time to set up his turrets. What I mean by this is, you must not let him nest down and get all three turrets up. Early game he is weak as at level one he can only hold one turret at a time. By level nine (if he is maxing his q first as any heimer should) he will have maxed his q and will be able to have three turrets in his inventory at a time. Focus. His. Turrets. As soon as he sets one down destroy it. It will shoot a laser but is easily dodgable if there is only one. After you dodge the lazer let the minions tank and destroy the turret. On top of this crippling him in lane it will also net you five gold per turret destroyed which stacks quickly.
Ok at this point if he is a good heimer he is going to notice what you are doing and instead of placing turrets he is going to save them and proabably start maxing his rockets. This is good, you have now taken out his defenses and he has to switch from a bunkered down playstyle to an assasin type play. Just stay behind your minions at all times and poke him down, pre level 6 you can all in him easily and get a kill. This is your windw of opportunity, because like most mid mages, or assasins after level 6 things become tricky. At this point after level six if you try to all in him, any sensible heimer will just place an ult turret down the minute you flash in then you are dead. You must now bait him. Act as if you are going in and bait the mega turret out. Then get the hell out of there and laugh as he has wasted his ult.
When facing a heimer you must make it your priority to not allow him to nest up, or once he has all three turrets up its going to be almost impossible to kill him if he is a good heimer, ESPECIALLY after six.
Now lets say the worst has happened. He has gotten a few kills on you, he has you to the tower and is safely nested. Do not engage. Farm as much as possible, avoid his pokes, and do not die. That is your new objective. Consider this lane lost and farm until teamfight. If you're jungler is bad, tell him not to gank as we do not want to feed heimer. Tell him to pressure the other lanes hard and push objectives. Understand when a lane is lost, it does not mean the game is lost. You will need to play smart.
Now remember how I said if your jungler is bad? Well if you're jungler is good we have a few options. If we have a tanky jungler well my goodness he can just waltz up into heimers house and kick the poor boy out! Especially if heimer has over extended the lane. See the problem with heimer is he has no escapes, except flash. If you can make him feel threatened and run away your jungler can catch him out and pick up the kill, or vice versa. Jarvan and lee sin work nicely, lee sin especially can q into heimer and kick him out of the turrets allowing you to get the kill.
In ending, heimer is good at what he does! He is one of my favourite champs. Is he op? Nope, he has weaknesses like any other champ. You just need to understand those weaknesses and play on them. Hope that helped :)