Fique atento à sua versão PHP, pois uso 5.5 e nos testes não tive este problema! Meus testes deram assim:

    echo json_encode($json, JSON_UNESCAPED_UNICODE);

> [{"id":"1","nome":"Porto Alegre","estado":"RS"},{"id":"2","nome":"Rio
> de janeiro","estado":"RJ"},{"id":"3","nome":"São
> Paulo","estado":"SP"}]

    echo json_encode($json);


> [{"id":"1","nome":"Porto Alegre","estado":"RS"},{"id":"2","nome":"Rio
> de janeiro","estado":"RJ"},{"id":"3","nome":"S\u00e3o
> Paulo","estado":"SP"}]