Hmm, może coś w ten deseń, choć pewnie da się prościej - jakiś niewyspany jestem

:
Tworzysz tabelkę users_online z 2 polami: user_id (integer, auto_increment) oraz time (integer).
//$sql - obiekt PDO
$sql->query("DELETE FROM users_online WHERE time<'".($_SERVER['REQUEST_TIME']-300)."'");
if(is_set($_SESSION['user_id']))
$sql->query("UPDATE users_online SET time='{$_SERVER['REQUEST_TIME']}' WHERE user_id='{$_SESSION['user_id']}'");
else
$_SESSION['user_id'] = $sql->query("INSERT INTO users_online (time) VALUES ('{$_SERVER['REQUEST_TIME']}')");
$online = $sql->query("SELECT count() AS online FROM users_online");
...
To tak na szybko pisane, ale mam nadzieję, że łapiesz idee. Należałoby oczywiście opakować w jakąś ładną klasę, dodać buforowanie w sesji, bo bez sensu kasowanie i pobieranie co odświeżenie.
edit:
Już widzę błąd, powyższy kod nie policzy osoby, której sesja nie zdążyła wygasnąć, a już została skasowana z bazy, więc musiałbyś i to sprawdzać, może jednak pierwszy pomysł był lepszy