Unfortunately I don't see any real way to avoid suid here, otherwise neat experiment. Posix ACLs might help, but the crucial part is prefixing the username to the message which requires privilege
Lots of unix facilities are criminally underutilized in modern systems
Run a daemon with the right userid to do the writing, and have it make a pipe device for each user to write lines into.
I don't know how much effort is meant to be put into securing this from impersonation, but info can be pulled out of /proc/ if the permissions are set up right.
Lots of unix facilities are criminally underutilized in modern systems