Buenas noches,
¿Como podría ejecutar esta consulta de una forma constante?

Mark_Disconnected()

        function Mark_Disconnected()
	{
		$timestamp_now = date('Y-m-d H:i:s');
		$timestamp_now = strtotime('-15 minutes', strtotime($timestamp_now));
		$timestamp_now = date('Y-m-d H:i:s', $timestamp_now);
 
		$con = Connection('A', 'B');
		$query = $con->prepare('UPDATE users SET connected = 0, sid = null WHERE connected = 1 AND '.($timestamp_now).' >= last_activity');
		$query->execute();
	}
 

La idea es hacerlo sin sockets, una de las soluciones podría ser un timeout de javascript que llama a una función ajax y una vez que se complete la solicitud "success:" se inicia otro timeout con la misma función... No se si esto está bueno o se sobre carga el servidor.

Realmente es algo con lo que estoy renegando hace rato ya.

Desde el vamos tenes un gran problema, y es que el protocolo HTTP 1.1 esta pensado y diseñado para ser desconectado:
se abre la conexion, se recibe la peticion HTTP, se procesa, en envia la respuesta HTTP y se cierra la conexion.

Por eso surgieron cosas como Socket.io para mantener una conexión activa. Eso de tirar de ajax dentro de un timeout solo da problemas, no tanto en el server sino en el propio cliente, por la naturaleza asíncrona de JS. Si no esta perfectamente programado y diseñado vas a terminar desbordando la cola de mensajes de JS (messages queue). Y ni hablar de los posibles huecos de seguridad que suponen llevar toda al logica de tu aplicacion a un simple timeOut que sera enviado en limpio al cliente.

Podrias llegar a usar ajax + timeOut, pero tendrias que hacer todo de forma sincrona y te digo que dominar la asincronia de js es mas difícil que dominar socket.io 

Por que no queres usar sockets que es justo la herramienta que necesitas implementar?