Redirecionamento header

Já li diversos posts como o http://forum.imasters.com.br/topic/507098-erro-warning-session-start/?p=2005699

Meu erro é o "Cannot modify header information - headers already sent" que acontece por ter html antes do meu 'header("location: index.php?msg=3");'

Tenho uma página com uma tabela contendo um menu e uma área central que é exibido o conteúdo principal redirecionado pelo menu. Em uma dessas páginas que é inserida pelo 'include', tem uma verificação de permissão que caso não seja atingida, vai redirecionar o usuário para outra página.

No servidor local ele funciona normalmente, mas no servidor online ele da o erro e exibe a página mesmo o usuário não tendo permissão (pq não é redirecionado).

Eu poderia colocar um 'die();' mas eu queria o redirecionamento.

Vai dar certo se eu substituir o php 'header()' pelo javascript 'location.href', mas isso seria gambiarra?

echo "
 <script language= 'JavaScript'>
 location.href=\"index.php?msg=3\"
 </script>

";

Alguma outra idéia?