Non-Hermitian matrices are ubiquitous in the description of nature ranging from classical dissipative systems, including optical, electrical, and mechanical metamaterials, to scattering of waves and open quantum many-body systems. Seminal K-theory classifications of non-Hermitian systems based on line and point gaps have deepened the understanding of many physical phenomena. However, ample systems remain beyond this description; reference points and lines are in general unable to distinguish whether multiple non-Hermitian bands exhibit band crossings and braids. To remedy this we consider the complementary notions of non-Hermitian band gaps and separation gaps that crucially include a broad class of multi-band scenarios, enabling the description of generic band structures with symmetries. With these concepts, we provide a unified and systematic classification of both gapped and nodal systems in the presence of physically relevant parity-time (PT) and pseudo-Hermitian symmetries using homotopy theory. This uncovers new fragile phases and, remarkably, also implies new stable phenomena stemming from the topology of both eigenvalues and eigenvectors. In particular, we reveal different Abelian and non-Abelian phases in PT-symmetric systems, described by frame and braid topology. The corresponding invariants are robust to symmetry-preserving perturbations that do not close band gaps, and they also predict the deformation rules of nodal phases. We further demonstrate that spontaneous PT symmetry breaking is captured by a Chern-Euler description, a fingerprint of unprecedented non-Hermitian topology. These results open the door for theoretical and experimental exploration of a rich variety of novel topological phenomena in a wide range of physical platforms.