You need to find a wild Chansey in the centre or north area of the Safari Zone (1% chance to encounter). You need to then catch the Chansey (4.9% chance) and see if it has the Lucky egg (5% chance). Its really hard but its the only way to get a lucky egg in Fr/Lg.
So you can get one before the E4 but its just really hard
Hope I helped. Source Safari zone encounter rates