How can a wavelength be defined for a laser where a photon's travel distance over a pulse duration is less than a wavelength? Femtosecond laser pulse are widely used in experimental physics. Femtosecond lasers like Nd:YAG systems produce coherent light at wavelength 1053nm. The distance traveled by a photon in 1 fs is 300nm; this means that a single pulse may be too short respect to the wavelength. In this way I think is impossible to define a single spectral line for the light emitted by the laser. 
So, what does it mean when we talk about wavelengths for femtoseconds laser pulses?
 A: The key thing to keep in mind here is the uncertainty principle, in its uncontroversial time-frequency form,
$$
\Delta t\: \Delta \omega\gtrsim 1,
$$
where $\Delta t$ is the duration of the pulse, and $\Delta \omega$ is the bandwidth of the pulse, i.e. the width of its spectral distribution. For short pulses, this requires that the spectral distribution be correspondingly broad, and if the width of the pulse is shorter than the center-wavelength period, then this typically means that the bandwidth $\Delta \omega$ is of the order of, or larger than, the center frequency $\omega_0$. However, that does not prevent the pulse from having such a center frequency.
It is much easier if you put this in an explicit mathematical form, with a gaussian envelope: in the time domain, you have the envelope multiplying some carrier oscillation, with some carrier-envelope phase $\varphi_\mathrm{CE}$,
$$
E(t) = E_0 e^{-\frac12 t^2/\tau^2} \cos(\omega_0 t+\varphi_\mathrm{CE})
$$
and then it is trivial to Fourier-transform it to the frequency domain, where you get two gaussians centered at $\pm \omega_0$:
$$
\tilde E(\omega)
=
\frac{1}{2} \tau E_0\left[
e^{+i \varphi_\mathrm{CE} }
e^{-\frac{1}{2} \tau ^2 (\omega +\omega_0)^2}
+
e^{-i \varphi_\mathrm{CE} }
e^{-\frac{1}{2} \tau ^2 (\omega -\omega_0)^2}
\right]
.
$$
So, how does this look like? Well, here is one sample, with the carrier-envelope phase set to zero, of how the spectrum broadens as the time-domain pulse length shrinks,

but the thing to do is to play with how the different parameters (and particularly the carrier-envelope phase $\varphi_\mathrm{CE}$) affect the shape of both the time-domain pulse and its power spectrum. As you can see, when the pulse length is shorter than the carrier's period, the role of the carrier loses a good deal of its significance, but it can still be an important part of the description of the pulse.

In the real world, though, pulses are much messier than just the width and the carrier-envelope phase, and if you really are in the few-cycle regime with real-world pulses then you need to worry about much more than just the pulse width, and the whole shape of the pulse comes into play ─ often involving substantial ringing in pre- and post-pulse oscillations. When you actually get down to few-femtosecond pulses, the state of the art of how short and clean (and well-characterized) you can get the pulses looks something like this:

(from Synthesized Light Transients, A. Wirth et al., Science 334, 195 (2011); this is real measured-then-inferred data of the pulse shape, as described here).
As mentioned, in the comments, when people in the literature talk about ultrafast femtosecond pulses, they are not one femtosecond long, but a bit longer: they tend to be supported on a 800nm Ti:Sa laser system, whose period is about 2.6 fs, and Full-Width at Half-Max pulse lengths can get down to 5 fs and, with intense effort, to the single-cycle regime. It is mathematically possible to produce shorter pulses (with due consideration to the zero-area rule), but for femtosecond laser systems this is generally limited by the Ti:Sa amplifier, whose bandwidth is about one octave (which lets you get down to pulse lengths of the order of the carrier's period, but not shorter) but then it stops. You can extend the cut via supercontinuum generation in a fiber, you're going to need to fight, hard, for every little bit of extra bandwidth.
If you wanted to have a shorter pulse at the same carrier frequency, you would need to work out exactly what spectrum you needed (which, for pulses shorter than the carrier's period, would extend from close-to-zero to many times $\omega_0$) and then find an oscillator and amplifier with that bandwidth. You would then still need to compress and pulse-shape and phase-control your pulses, but without the bandwidth, it's mathematically impossible.
Shorter pulses are possible ─ the record, I think, is currently in the vicinity of about 150 attoseconds or so ─ but these are supported by carrier frequencies that are much higher, in the XUV range, typically produced via high-order harmonic generation, and they are typically many cycles long, so that they don't fall into the issues raised by your question.
A: There are two ways of looking at these kind of phenomena; in the time domain or in the frequency domain. A femtosecond pulse in the time domain corresponds to a broad range of frequencies in the frequency domain. Indeed, this is how one creates femtosecond pulses, by locking many cavity modes, that all have slightly different frequency (and thus wavelength), together. You can still refer to the central or dominant frequency component that makes up a short laser pulse, but the pulse itself is by no means monochromatic. The limit in pulse duration can be converted to the optical path length of this central wavelength and is typically around two optical cycles. One can refer to the wavelength or frequency of a femtosecond pulse, but one should keep in mind that it contains a large number of frequency (wavelength) components (often octave spanning).
A: Laser light is produced by stimulated emission: when an electron pumped to a high energy level deexcites to a lower energy level. The energy difference is the energy of the light, which is related to its wavelenth by E = hc/$\lambda$. This quantum of energy is produced as soon as the stimulated atom deexcites and emits. It doesn't matter how far it has travelled: as soon as it has been emitted it has an energy and therefore a wavelength.
Think about what a wavelength actually is: it's the distance an electromagnetic wave travels while the electric (and magnetic) field components perpendicular to its direction of motion complete 1 oscillation. Since it travels at c, this is just a measure of the oscillation time = $\lambda$/c. The fields exist as soon as it starts oscillating; the wave doesn't need to travel some distance before it's wavelength is defined. The wavelength just describes how long the fields will take to oscillate.
