Its thought to be a 3rd buy must for ezreal, and I thought the same. But with the new runes it opens up the game for lots of new build paths and I personally always thought black cleaver would be perfect for ezreal as he is an AD spell caster, but it didnt make sense last season as you overcaped in cdr and it didnt gave you as much as other items did.
Now cleaver gives you:
64 AD
400 HP
20% CDR (24 AD)
24% BASE armor penetration
This is perfect for Ezreal as although he is an AD spellcaster lethality makes him fall off extremely and not make any damage to real tanks. My main problem with building BoRK third now his attack speed nerf, its quite noticeable that you dont attack as fast as you used to and making BoRK not as effective as it used to. Still most probably BoRK does more damage overall (depends who youre facing) but dont forget the 400 health extra youre getting with cleaver it makes for the other adc virtually impossible to duel you mid game so he has to either run from you or be bursted down. This build makes you very present during teamfights and very difficult to kill when youre reseting your E cd effectively.

This build is about presence with your Q, abuse your extremely high range quit your Q and mobilty to make the most out of it. If you cant hit Qs for **** your damage will fall off. Its best point is that it allows you to deal damage very comfortably as you can rely on you not getting one shot. This allows you to dps more effectively if you know how to use your E or your mobility in general. With elixirs you can realistically can have somewhere around:
450-550 AD
2600 HP (3300 HP effectively with deaths dance passive)
1.19 no passive AS
1.63 passive AS