Estimating the wavelength of a sinusoid
The first thing to note is that the LMA algorithm is an estimator, and tries to minimize error in the least squares sense, between your data, and a model function of variable parameters. 

Typical of LSE based frequency estimators, you need to seed them at values close to the global minima of the cost function, otherwise they will find another local minimum to lock on to, and hence they need to be seeded properly, or 'in the ball park', ostensibly using some apriori information. How to attain this a-priori information? See below.


  This solution worked wonderfully for toy data that I generated, but it
  fails quite frequently on real data, because of the noise. The
  amplitude of the noise can be as large (at most) as the amplitude of
  the signal.


LMA will provide you with an amplitude, phase, and frequency estimate in the LS sense. Of course, the more noise there is in your data, the worse off this estimate is. This is why you will need to pre-process your data to remove as much noise as possible, before the application of the LMA. 

You mention zero-padding your data, and while this will not increase your frequency resolution, this will certainly increase your frequency granularity. (Interpolation in the frequency domain). With those facts, I would attempt the following solution:


Pre-Process the data via an (FIR) Band-Pass Filter centered around my frequency of interest. 
Perfrom a zero-padded FFT so as to ascertain the peak frequency of interest within the BPF'd data's band. 
From this peak, ascertain the frequency, amplitude, and phase, with which to seed LMA with. (Note, make sure to remove the phase offset the BPF filter added for the seeding value).
Run the LMA.



  I'm guessing you mean throw away the highest frequency components etc?
  Would the statistics of my noise matter in that case? I can assume
  it's gaussian, but that may not be strictly true in all cases


The statistics of the noise does not matter in this case. All you are doing is removing frequency bands where noise exists, independent of their statistics. In this way, you are not utilizing DFT bands where your signal does not exist, and retaining the DFT bands where your signal exists.