Actually you do get new moves, but they overwrite the oldest one. So if a Pokemon learns Earthquake, Fissure, Protect, Reflect, Sand Attack in that order, then Earthquake would get replaced by Sand Attack!
And yes, levelling with the Lucky Egg or Exp Share is much better at least for the lower levels. A level 1 Pokemon with Exp Share will grow 15-20 levels after just one Audino battle!