Você pode enviar uma mensagem para todos os consoles com a parede de comando.
Para enviar notificações sob X, há notificar-enviar que envia uma notificação para o usuário atual na exibição atual. (De sua pergunta, eu acho que você já conhece este.) Você pode construir sobre isso com alguns scripts bash. Basicamente você tem que descobrir quais usuários estão em quais X-Displays. Depois de obter essa informação, você pode usar notificar-enviar assim:
DISPLAY=:0 sudo -u fschmitt notify-send "Message"
Onde fschmitt é o usuário na exibição 0. Você pode analisar a saída do comando "who" para localizar todos os usuários e suas exibições. A saída parece com isso
[edinburgh:~]$ who
markmerk3 tty7 2010-09-23 10:59 (:0)
markmerk3 pts/1 2010-09-30 13:30 (:0.0)
fschmitt pts/2 2010-10-08 11:44 (ip-77-25-137-234.web.vodafone.de)
markmerk3 pts/0 2010-09-29 18:51 (:0.0)
seamonkey pts/6 2010-09-27 15:50 (:1.0)
markmerk3 pts/5 2010-09-27 14:04 (:0.0)
seamonkey tty8 2010-09-27 15:49 (:1)
markmerk3 pts/13 2010-09-28 17:23 (:0.0)
markmerk3 pts/3 2010-10-05 10:40 (:0.0)
Veja, existem dois usuários executando sessões X, markmerk3 no display 0 e seamonkey no display 1. Eu acho que você precisa grep para tty [0-9] * e então assegure que no final da linha existe ( : [0-9.] *) Para se livrar dos logins do console e extrair o ID de exibição da string entre os parênteses.