You can send a message to all consoles with the command wall.
For sending notifications under X there is notify-send which sends a notification to the current user on the current display. (From your question, I guess you already know this one.) You can build upon this with some bash scripting. Basically you have to find out which users are on which X-Displays. Once you got this info you can use notify-send like this:
DISPLAY=:0 sudo -u fschmitt notify-send "Message"
Where fschmitt is the user at display 0. You can parse the output of the "who" command to find all users and their displays. The output looks like this
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)
You see, there are two users running X sessions, markmerk3 at display 0 and seamonkey at display 1. I think you need to grep for tty[0-9]* then assure that at the end of the line there is (:[0-9.]*) to get rid of console logins and extract the display id from the string between the parentheses.