\t {Analytic Method}
Assume $\chi$ primitive now.
If $$
K_{n,\chi}:=(-1)^{n-1}\, 2 n!\left(\frac{N}{2 i}\right)^n
$$
then
$$
B_{n,\chi}=\frac{K_{n,\chi}}{\pi^n\,\tau(\chi)}\;
L(n,\overline{\chi})
$$
There is a simple formula for a $d$ such that $d \cdot B_{n,\chi}$ is
an algebraic integer (analogue of Clausen and von Staudt).
For $n$ large we can compute $L(n,\overline{\chi})$
{\em very quickly} to high precision; hence we can compute
$B_{n,\chi}$ (at least if $\Q(\chi)$ isn't too big,
e.g., $\Q(\chi)=\Q$ wouldn't be a problem). (Note, for
small $n$ that $L(n,\overline{\chi})$ converges slowly; but
then just use the power series algorithm.)
Compute the conjugates of $d\cdot B_{n,\chi}$ approximately;
compute minimal polynomial over $\Z$; factor that over $\Q(\chi)$,
then recognize the right root from the numerical approximation
to $d\cdot B_{n,\chi}$.