If that is the only reason for the non-Hermitian-ness, then you are have an easy task — the matrix A=iH is anti-Hermitian, not Hermitian, but it is still normal with orthogonal eigenvectors.
More simply, if you have a matrix A where H=-iA is Hermitian, then simply diagonalize H=Q\Lambda Q^* and use e^A = e^{iH}=Qe^{i\Lambda}Q^*.
Furthermore, if A is tridiagonal, then H is tridiagonal and Hermitian. If H is not already real, there is a trivial change of basis to make the problem real symmetric tridiagonal. So you can always use the efficient real-SymTridiagonal eigensolver.