Can a free-falling aircraft with no horizontal (or minimal horizontal velocity) start up and fly to safety?
Rather obviously, both of these situations are far from likely to occur. As a result, the following is just idle (but hopefully informed!) speculation — I don't recommend experiments! 


I'm going to be a little bit cheeky in answering this question -- you've asked if it's possible for “a fixed wing aircraft to [...] get the engines up to speed and fly off.” I'll answer “Yes, but it depends on the aircraft.” For the fixed wing aircraft I usually fly, a K-21 glider, getting the engines up to speed is a doddle — it’s powered by gravity (and essentially stays aloft by the sun). What matters here is the stall speed of the aircraft in question, and how quickly the pilot could recover from the ‘upset’ of being kicked off the top of a tall building, and land somewhere sensible (which can only realistically happen once the aircraft is not stalled). If the relative airflow over the K21’s wings is about 35 knots (40 mph, 65 kph) or greater, they generate enough lift to keep it airborne (and going about 30 m forward for every meter down). 


If we assume that you’re a free-falling body, Newton (in the form of $v=u+at$) says that it’ll take about 1.8 seconds to reach that speed, and you’ll fall ($v^2=u^2+2as$) about 16 meters during that time. 

Of course, you’ll be pointing nose down at the ground, accelerating, and needing to do something about it — which will take time, and, more importantly distance. But, in the grand scheme of sky-scrapers, mountains and cliffs, 16.2 m isn’t that high. Incidentally, for this reason, bungee launching is a traditional method of getting gliders airborne in parts of the world with big hills — a team of runners using glorified elastic bands shoot brave pilots into the blue yonder, as illustrated by the picture below (at the Long Mynd). 



So, given that a hill is enough height for a sailplane to take off, possibly for a few hours on a good day, I’m reasonably sure that something like the John Hancock Centre would provide more than enough time for a pilot to recover from an odd attitude, loop forward to a nose-down dive, recover smoothly from it, and fly away (from the big building behind him).

The gif you linked to featured what looked a lot like a small private jet. I defer to the others on this site with a lot more turbofan experience than I, but I’ll just say this: given an hour that I spent in a 777 simulator, twenty minutes were spent going from “cold and dark” to pushback, I suspect you’d have a much harder time doing it. Of course, rapid engine starts are possible in some aircraft. It depends a lot on the exact circumstances you're asking (and passenger jets tend not to be designed for inverted flight, for example). 


By all accounts, this situation isn’t probably going to be very recoverable. If the blades are stationary when the aircraft starts falling, they’ll be fully stalled, resulting in a low-rotor RPM stall, which, depending on the brand of helicopter may not “be recoverable” (e.g., even with a working engine, Robinson helicopters are generally not recoverable from a very low rotor RPM stall). Autorotation is the driven motion of the rotor by the air falling through it, but, as pointed out, fully-stalled blades at any angle will not generate much torque (or lift), and therefore be unable to arrest the rate of descent of the falling aircraft. I presume that the only exception would be a fuselage that could provide lift through another means, such as the V-22 Osprey.