Our database design currently incorporates tracking fields on every single table:
CREATED_ON_TIMESTAMP
CREATED_BY
MODIFIED_ON_TIMESTAMP
MODIFIED_BY
I find this pretty ugly... is there a better way to handle it? The rationale in this case was that it's easier to deal with as columns in a table. Of course the obvious drawback is that there's no way to track a delete...

I don't think the original designer considered that.
I considered creating an audit table that stores this information, but then you also need to keep the key fields somehow, it's a little tricky to make it generic.