I am lvling a HC barb he's lvl 16. I rolled 2 Leoric's Crown's from Kadala (both lvl 16) and both rolled WITHOUT socket. And when I bring them to Myriam to change the stats to roll socket. Their is no option for it to roll WITH a socket.
Leoric's Helm can roll with a socket at level 18 (I was curious so just tried it on a level 18 character and Kadala gave me 3 right off).
For leveling a new toon... you should be level 20 before you fight the skeleton king (in campaign mode) to get the helm as a guaranteed drop. He can drop it before level 20 but you are much more likely to get some other legendary item.
Side note: If you don't care about the leveling helm but you want a decent legendary you should fight him at level 18-19. High chance the drop will be a weapon that either has a socket or can be enchanted with a socket.