It doesn't matter whether or not the perturbation is Hermitian. One poses the eigenvalue problem in block form with one block corresponding to each unperturbed eigenvalue and obtains a coupled system for the block coefficients. For simplicity assume that in a basis where the unperturbed Hamiltonian is diagonal, the perturbed Hamiltonian is $H=\pmatrix{H_{11} & H_{12} \cr H_{21} & H_{22}}$, where $H_{11}$ is the block corresponding to the degenerate eigenvalue $E_0$ of interest. Then the eigenvalue problem takes the form $$(E-H_{11})\psi_1- H_{12} \psi_2=0,$$ $$ -H_{21}\psi_1+(E- H_{22})\psi_2=0.$$ Here the dimension of $\psi_1$ is the algebraic multiplicity of the unperturbed eigenvalue $E_0$. By construction, $E-H_{22}$ is nonsingular for $E$ close to the unperturbed eigenvalue $E_0$. Thus we can formally solve the second equation for $\psi_2$ and insert the result into the first equation. This results in a nonlinear eigenvalue problem $H_{red}(E)\psi_1=0$, which is still exact. First order perturbation theory amounts to linearizing $H_{red}(E)$ around $E=E_0$ and then solving the resulting linear eigenvalue problem.
A detailed exposition of perturbation theory in the presence of degeneracy is given in
Klein, D. J. "Degenerate perturbation theory." The Journal of Chemical Physics 61.3 (1974): 786-798.