Migrating DNS provider when having high NS-record TTL

Solution 1:

can I safely delete the zone at provider A, even though NS-record TTL might not have expired for clients?

No. The old servers must remain online for the duration of the TTL associated with the NS records.

What exactly happens when clients contact NS provider A and it doesn't respond with authority anymore? Provider A should just call Provider B and relay a non-authoritative response to the client, right?

No, authoritative servers do not relay responses between each other. If the recursive server has cached the old nameserver data, it will attempt to communicate with the old servers. If all of those authoritative nameservers fail to respond, or return REFUSED, your domain is dead in the water until the old data is invalidated from cache.