Well they'll need to have the program, it's just no possible otherwise. However, I believe most version of windows come with a program called WinPopup which can be used to send messages over the LAN. They'll need this program open to see any message you send to them.
If your running windows you can use Net Send by typing in a command window net send then the login name of the user or their I.P. address and then the message. Like so
net send user_a Hello
I have tried the Akeni Web Chat and your users does not need to download any program to access the program. An alternative is to use the Akeni LAN messenger, but this requires a download. More information can be found from their web site at http://www.akeni.com