Hola, ¿qué tal?
Abre tu archivo .php con
Notepad++ y ve a
Codificación > Convertir a UTF-8 sin BOM. Puedes usar otros editores o IDEs, pero personalmente recomiendo ese. La función header() de PHP no debería ser necesaria en este caso.
Si sigues teniendo problemas, ejecuta la siguiente consulta justo después de haberte conectado a la base de datos (supongo que usas MySQL):
Un saludo.