On Air France 447, what would have been the lowest altitude to initiate recovery after the stall developed?
For the stalled flight to recover, the nose needs to be pointed in the airstream, and then the aircraft pulled up with load factor below the ultimate load. From the accident report:


  The recordings stopped at 2 h 14 min 28. The last recorded values were a vertical speed of -10,912 ft/min, a ground speed of 107 kt, pitch attitude of 16.2 degrees nose-up


Initial situation. 

From earlier on in the report we can conclude that these values were typical for the complete stall from 36,000 ft to impact, except for the pitch attitude which was around zero for most of the stall. The flight state parameters were therefore: 


Vertical speed was 10,000 feet/min = 51 m/s
Horizontal speed was 100 kts = 51 m/s, which constructs an airspeed of 72 m/s.
The engines were at TO thrust, creating a nose-up moment, compensated by the nose-down moment of the airstream hitting the horizontal stabiliser. 
The automatic trim is retained in alternate law, so the stabiliser is trimmed full LE down = 14º. 
Elevator is fully up = 30º on top of the trim - it is almost aligned with the stalled airstream. 




Nose down manoeuvre. 


At 72 m/s the aircraft is at about TO speed, and nose rotation speed should be comparable to TO rotation speed - a bit slower because one side of the elevator is stalled. It takes perhaps 5 - 10 seconds to rotate the nose down 45º (an estimated assumption from my part). 
When at 45º nose down, gravity accelerates @ 0.7g and the engines at perhaps 0.25g. At this acceleration airspeed builds up with around 1 g = 9.8 m/s every second. If we take averages for nose down manoeuvre time and acceleration, airspeed builds up with 4.9 m/s for 7.5 seconds = 37 m/s. So when the nose is aligned the airspeed is about 110 m/s, but still accelerating fast. 
During the 5 - 10 seconds nose down manoeuvre, the aircraft loses about 1,000 - 2,000 ft in altitude


Speed increase

Before the aircraft can be pulled from the dive, the true airspeed needs to be brought to the manoeuvre speed $V_a$. From the A330 FCOM:


  The load alleviation is only available when :
  
  
  The aircraft speed is above 250 knots.
  The FLAPS lever is in the 0 position.
  In normal or alternate law flight mode.
  


Above 250 knots the load alleviation system is active, in order to keep the maximum load factor at 2.5g. The manoeuvre speed (or cornering speed in military speak) seems to be set at 250 knots = 128 m/s. At 1g acceleration, it takes 2 seconds to increase speed from 110 to 128 m/s, during which the aircraft loses altitude of 500 ft:

$$\Delta h = sin(45) \cdot (V_0 \cdot t + \frac{1}{2} \cdot a \cdot t^2)$$

Pull-up manoeuvre. 

Then during the pull-up manoeuvre, the load factor must stay under the limit load = 2.5g. 1g is taken up by gravity, and there is 1.5g available for the pull-up manoeuvre.

$$ m \cdot \Delta n \cdot g = m \cdot \frac {V^2}{R} \Rightarrow R = \frac {V^2}{\Delta n \cdot g}$$

With the values established above, we get R = 10,000 / (1.5 * 9.81) = 1,100 m = 3,300 ft. But that is at constant airspeed of 128 m/s, in reality the airspeed will still pick up at the beginning of the manoeuvre and the radius will be higher - let's say 4,000 ft. The velocity vector of the plane was 45º pointing downwards, so half the radius is used. This is from the moment the AoA is close to zero, which it needs to be in order to start the pull-up, which increases AoA again. 

My estimate for the altitude required for a successful pull-up from the stalled situation, is therefore 2,000 + 500 + 2,000 = 4,500 ft if they end up skimming the tops of the waves. If they know exactly what to do, time things perfectly, and manage airspeed perfectly. The aircraft is protected against pulling too many g's, so once the nose is aligned the flight crew can pull the stick fully aft and let the aircraft manage the minimum pull-up radius. If for instance the pull-up is initiated 1 second later than the 2 secs estimated above, the airspeed increases to 138 m/s and the pull-up radius becomes 1,300 m = 4,000 ft, plus the aircraft loses an additional 300 ft during the 1 extra second diving down under full power - this 1 second delay in initiating the pull-up requires another 1,000 ft.

Recovering from a fully developed stall is now trained in Level D simulators. Picture below is from a company that makes the flight model and instructor station extension for any flight simulator to train the manoeuvre. Disclosure statement: I have done business with them in the past.