Invuln Haxdash - Zelda does have an invulnerable haxdash on every stage. This is performed by: Releasing ledge, fast falling one frame, jumping towards stage, airdodging at a 45 degree angle back on frame 19/20, then fastfalling the second frame of airtime. This is frame-tight but has wiggle. Slight variance in edge release time after CliffCatch or fastfall after dash time will cause vulnerable frames.
Yoshi's story has a much simpler invuln haxdash due to its slippery angled edge. You do not need to input a fastfall for full invuln on yoshis. Frame timing is also slightly more lax.