How does stall depend on angle of attack but not speed?
I believe you are confusing the wing angle of attack with the pitch of the aircraft.  Aircraft moving at a slow, near-stall speed, despite pointing the nose up, will still be traveling more or less horizontally.  Their VSI instrument will read near zero.  Whereas, if you take an aircraft moving quickly and pull the nose up to the same angle, the aircraft will, obviously, climb rapidly.

Why does this matter?  The angle of attack is defined based on the wing's motion through the relative wind.  The wing's orientation relative to the ground isn't involved in the definition in any way.  When the aircraft as a whole is climbing, the relative wind is coming down from above.  As a result the angle of attack is reduced, compared to what it would be if the plane were not climbing.

Just to show some quick numbers, suppose you took an aircraft moving at 100 kts in still air and pulled the nose up so that you are now climbing at 3,000 FPM (most aircraft will lose speed doing this, but the math is valid until the airplane slows down).  $1knot\approx100FPM$, so you'll now have an upward vector of 30 knots.  Your 100 kt airspeed is now moving up at an angle.  A little trigonometry:

$$\sin(x)=\frac{30}{100}$$
$$x=17.46°$$

So, your angle of attack is 17.46 degrees farther away from stalling when climbing at 3000FPM than it would be if your aircraft had the same pitch but was in level flight.

However, few aircraft have the engine power to sustain a climb at this rate.  The aircraft will bleed off speed, and as the speed bleeds off, the aircraft will slow, the climb rate will decrease, the aircraft's velocity will become closer to horizontal, and, eventually, the aircraft will stall if the pitch is held constant.