The feature you're describing is similar to a technique known as server-push. What you're asking to do is a very tricky thing for a web app (especially for PHP, which is built around the idea of a request that gets served and the script terminating).
HTML5 is introducing technologies such as websockets for maintaining a persistent connection to a server, you could look into websockets as a solution, but it's a brand-new technology and I don't think the spec is even finalized yet, so it will only be implemented in the very latest versions of browsers, if at all.
You've already mentioned AJAX polling (driven by setInterval), but you've also noticed that it's problematic. You're right of course, it is, local data can become stale in the interval between polls, and you'll generate a lot of traffic between the server and any open clients.
An alternative is so called "long-polling". The idea is the client starts an AJAX session with the server. On the server the script invoked by the client basically just sits there and waits for something to change. When it does, the server notifies the client by sending a JSON/XML/whatever response and closing the AJAX session. When the client receives the response, it processes it and initiates a new AJAX connection to wait for another server response.
This approach is almost instantaneous, because data gets pushed to the client as soon as it's available. However, it also means lots of open connections to the server and this can put the server under a lot of load. Also, PHP scripts aren't really meant to run or sleep for a long time due to the request-response model the language is built around. It is possible, but probably not advisable to follow this approach.
How do I implement basic "Long Polling"? has some examples of the long-polling technique.
Good luck!