Hola,
Cita: tendía que crear un campo fecha con la fecha cuando se ha añadido o modificado y ordenarlo con eso??
Exactamente, pero puede que MySQL te ayude. Tiene un tipo de campo, el TIMESTAMP, que es como un datetime, pero que se actualiza automaticamente cuando haces un INSERT o un UPDATE del registro, sin tener que hacerlo especificamente. Asi no tendrias que cambiar tus consultas actuales de insercion y actualizacion de datos. Solo añadir el campo a la tabla y usar ese campo en tu consulta de ordenacion.
Mas info en
http://www.mysql.com/doc/en/DATETIME.html
Saludos.
PD: Como es una pregunta especifica de SQL, sin relacion a PHP, muevo el mensaje al foro de base de datos.