Certifique-se de iniciar o primeiro nó executando o seguinte comando:
service mysql start --wsrep-new-cluster
Inicie os próximos nós executando o comando:
service mysql start
Recebo exatamente os mesmos erros que o seu quando esqueço de adicionar o parâmetro --wsrep-new-cluster ao iniciar o primeiro nó.
Verifique esta página para obter detalhes:Iniciando o cluster
Apenas uma edição rápida:eu pessoalmente uso Galera com MariaDB e os comandos acima funcionam corretamente. Conforme você usa o MySQL, pode ser necessário alternar
mysql com mysqld nos comandos acima. Tente com os dois. 
