The question you're asking roughly translates to
What is the time of useful consciousness at 39,000 feet?. The answer is "About 15-20 seconds, once the pressure bleeds off." The FAA has a handy table for this:
From Chapter 16 of the Pilot Handbook of Aeronautical Knowledge.
You can get a PDF of Chapter 16 here, or you can grab the whole thing from the FAA
The Time of Useful Consciousness will vary depending on personal physiological factors (e.g. if you're a smoker your blood doesn't oxygenate as well - you will probably have less time. If you're a mountain climber in excellent shape and used to breathing rarified air on your climbs you'll probably have a little more time).
In the case of a non-explosive decompression (say a pressurization system failure) you'll probably have more time than this from the start of the event to the point where everyone is unconscious: the cabin pressure will take time to bleed off. Whether that time is seconds or minutes depends on the nature of the leak.
Presumably while the pressure is bleeding off the aircraft's systems will complain about the loss of cabin pressure and give the pilots a chance to address the problem (fix the pressurization system or descend to a safe altitude). Unfortunately the effects of hypoxia can start setting in before the crew realizes what's going on (which is one of the contributing factors in the loss of Helios Flight 522, which suffered just this kind of gradual depressurization).