"NP has to be somewhere between them but we have no idea where" – I guess that this state of affairs won't change much even if we prove P != NP?

I think that's unclear. A constructive proof of P != NP might yield insights into the "gap" between them.