Perché spedisci altri headers prima, se tanto devi/vuoi fare un redirect? Comunque, ammesso che non ne puoi proprio fare a meno (adesso non mi viene in mente un esempio di questo caso, ma non dubito che possa esistere) mi sa che ti tocca usare javascript.