Hello everyone, I am a decent player who got Gold in season 5 (before my internet became suck so I cannot play ranked anymore, just have fun on normal). This is my first time writing a guide, so please dont be (too) hard on me.
I have play a lot of game with Ezreal, both mid and adc, and loyal with his frosted build from the very start until now. I want to share my experience about the champion who I love the most with you. In my opinions, Ezreal has the most unique play style among the ADC, and his potential power is great.

Just take a typical rune page for ADC with AD marks, Armor seals, MR glyphs and AS quints. You can modify Armor seals with HP/HP per level, and MR glyphs with MR per level.

You can stack your Fervor of Battle very quickly and its deliver a super high dmg output, so I recommend to take 18-12-0 with all lane-sustain point (Feast and Vampirism). Your core item include Iceborn, so take Oppressor.
You can give 5 point to Battering Blows or spread it between BB and Piercing Thoughts.

First back: Get Tear asap because you need time to stack it. Use your Q every time it ups. With this build, you will have a hard time until you complete your cores, so dont forget to buy pink and some potion to have a not-too-hard childhood.
Core items: I prefer to get pick axe right after I have enough money because it will give me some dmg to trade and farm in lane, and get Manamune to stack it fully quicker. If you get fed, take sheen to dominate your lane earlier.

I have some play style for you, use it wisely. Thanks to Rito, Ezreal can ultilize many items and they are all good.
Hyper Cannon Mode: I prefer to get pick axe right after I have enough money because it will give me some dmg to trade and farm in lane, and get Manamune to stack it fully quicker. If you get fed, take sheen to dominate your lane earlier.
Defensive/Another Teemo: Your enemy will be super annoy with an un-catchable ADC version of Teemo with endless slow shot (and even if they can, you will still have great chance to walk away, wave your sexy butt into their faces)
Wave clear/ Tickling till death: If they have some annoying faceslap champions, go into this build. You can clear a wave from thousands mile while have a decent poke power. One tickling maybe fun, but tons of tickling will bury your enemies.

Max Q first, its your bread-and-butter skill. Max E after that and max W at last. Level up your ultimate whenever you can.
You can take W at 4 or at 8, it does not really matter in most cases.

Try to farm very safe until you got your core. Poke enemies if you can, but dont rush into trade because with a Tear build, Ezreal just slightly stronger than a gromp in early game. Moreover, dont forget to stack your passive before you going in a trade, his AS steroid is critical in win or lose a trade.
You can farm and stack your Tear/ Manamune safely with your Q from 1000 range, and if enemies force you to farm under turret it still quite simple. Dont hesitate to use E to last hit under turret.
After 6, if needed, use your ulti to farm. It has a quite low cooldown (not anymore in 6.4, btw, your q lowered it by 1.5 second every time you hit something, so dont worry).

Always remember that you are a professional "poke-er", melt your enemies down instead of jumping into their faces. Even his burst-potential is suprising considerable, Ezreal unique power still remain poke from a safe range. I recommend you to test it several time before taking a risky play.
Use your E wisely, it your trademark skill. It will distinguish bad, good, and great Ezreal players.
Try to mix your combo: Add an AA between all of Ez's skills will raise you to a new level with him. Your skill shot animation will eliminate the time between 2 AA and make it smoothly, beautifully, and deadly. For example: Q - AA - W - AA - E - AA - Q - AA.

I will add some vids here. Thank you for reading my guide!