That is only going to work if every single column of every single row in that table has been updated recently (within your log). You will not be able to recreate rows or columns within rows that have not been updated.

The only time I want to change an Update statement into an Insert statement is the first time the key shows up

You can just go ahead and try to update. If the update reports 0 affected rows (DBI->do tells you this), you have to change it to an insert and run it again. This way, you can let the DB keep track of "first times".

The second problem is that I need to be able to completely restructure the command

You could get away with a simplified insert (which just creates the row) and then running the original update. That would reduce the amount of intelligence you have to put into that update-to-insert query rewriter.