According to Bulbapedia, Lucky Egg can only be found in HGSS from wild Chansey. Chansey can only be found on Routes 13, 14, and 15 in Kanto and by using blocks in the Safari Zone, which requires the National Dex.
So unless you are able to trade a Lucky Egg to your game or somehow are able to obtain the National Dex, you are unable to get the Lucky Egg prior to the E4.
Hope I could help!