You could put a trigger on the table.
See MySql trigger docs here...
http://dev.mysql.com/doc/maxdb/en/a7/41ee0b605911d3a98800a0c9449261/content.htm
You could have this trigger insert into another table for each row that is inserted, updated or deleted.
You would then write a perl program to select from this new 'transaction' table.
This will keep you from doing full table scans off the actual table trying to determine the new records and gives you a way of knowing the records that were deleted.
Update:
Ok, dragonchild points out that triggers are not prime time yet. Can you change the API that does the Insert/Update/Deletes to the table? If you can then you can simulate a trigger by populating a 'transaction' table there. Deletes are the tricky part of your requirements and will require some kind of transaction queueing to manage.