You are right, the Publishing Queue only stores the most recent publish action for an item. The best way to get this information is to capture it in a custom database using the Event System. You can implement an event with the following signature:
..and implement your delegate method:
ItemFinishedPublishing to capture whatever information you require.
Note that this event is triggered only after successful publish/unpublish of an individual item (Page, Component, Taxonomy). If you want to have information about the whole publish transaction, you will need to investigate the following event signature:
Note that this event is triggered multiple times per transaction, as it goes through all the states (Queued for Publishing, Waiting for Transport, Deploying etc.), so you probably only want to log stuff for the end states;