O comando adequado para fazer isso é:
mysql -uroot -poldp4ssw0rd -e "SET PASSWORD FOR 'root'@'localhost' = PASSWORD('newp4ssw0rd');"
assumindo que oldp4ssw0rd e newp4ssw0rd são as senhas antigas e novas.
Você não precisa parar ou reiniciar o servidor MySQL a qualquer momento. Na verdade, o serviço precisa estar em execução para você se conectar a ele e emitir o comando acima.
Nota: este comando resolve seu problema; no entanto, em geral, não é uma boa ideia passar senhas como argumentos de linha de comando, pois elas podem ser vistas por outros usuários conectados.