How does a logic gate behave with an input changing faster than its propagation delay?
It really depends on how the gate is constructed.  For a completely accurate simulation, you have to do a transistor-level analog simulation.  However, it is possible to extract timing parameters from a transistor-level simulation and abstract them out a bit.  The output rise and fall times and propagation delays will depend on the input rise and fall times, output load capacitance, power supply voltage, temperature, and the state of the inputs.  Yes, it is possible for the same input transitioning to have a propagation delay that depends on the state of the other inputs.  These techniques are used in the timing models used in ASIC and FPGA design in both static timing analysis as well as timing-driven place and route.  

Fundamentally, the propagation delay is determined by how long it takes for the output to transition in response to a change at the input.  This depends on exactly how the gate is built at a transistor level.  For a single two transistor CMOS inverter, the propagation delay is determined by the analog electrical characteristics of the transistors and their parasitic capacitance.  The input will slew at some rate, then once the threshold is reached the output will start slewing.  If the input changes before the output finishes slewing, then the output will start to slew back the other way and you will end up with a highly distorted output.  So for a single inverter, the output for a change faster than the propagation delay would be an invalid logic level (i.e. x).  However, "gates" can be far more complicated than a single inverter.  For example, if you have a "gate" that is built from a string of 100,000 inverters, then the propagation delay of the whole unit will be 100,000 times the propagation delay of a single inverter and it is certainly possible to have multiple transitions 'in flight' at the same time, so long as these transitions are not faster than each individual inverter can handle.