LLC resonant converter with air core
Is it possible to do an LLC resonant converter with an air core
  transformer (wireless power transfer)?


Sure it is and I've actually done several in coupling power to electronics mounted on a spinning shaft.


  I've read basics about it but I've all read that they use some type of
  ferrite cores.


If you can use ferrite cores you get benefits in that you need fewer turns to generate the same magnetic field and you can use ferrite to prevent your generated field being "killed off" by excessive eddy currents in conducting metal that might surround the coils.

Your middle paragraph is correct as far as I can tell but there is an easier way to get to a solution that also considers how the magnetic field attenuates with distance. 

Consider this: -



The above does not consider tuning but tuning with capacitors has huge benefits. Firstly, the driven coil can be parallel tuned to produce a much bigger magnetic field for a given excitation current. The receiver coil also benefits from tuning too.


  I was thinking, in an air-core transformer, distance can change which
  means Lm (part of resonant tank) changes.


Yes, as distance gets bigger the coupling is smaller and the resonant frequency becomes wholly dictated by the transmit coil and its resonant capacitor. As distance shortens you get more coupling and if you plotted the frequency response (such as on a sim) you'd find two peaks emerging either side of the original resonance.

Changing the driving frequency can offer a means of regulation but remember you need a feedback mechanism from the receiver to tell the primary controller what the receiver voltage is.