The reason I claim this would be simple is that PostgreSQL is
almost already doing this. The way the data is stored on disk, every row has two transactions identifiers, xmin and xmax, which represent the transaction when that row was inserted the the transaction that row was deleted; rows, meanwhile, are never updated in place, so the old data stays around until it is deleted by a vacuum.
To demonstrate more tangibly how this works, I just connected to my database server (running PostgreSQL 9.1), created a table and added a row. I did so inside of a transaction, and printed the transaction identifier. I then queried the data in the table from a new transaction, showing that the xmin is set to the identifier of the transaction that added the row.
Connection 1:
demo=> create table q (data int);
CREATE TABLE
demo=> begin; select txid_current();
BEGIN
189028
demo=> insert into q (data) values (0); commit;
INSERT 0 1
COMMIT
demo=> begin; select xmin, xmax, data from q;
BEGIN
189028|0|0
Now, while this new transaction is still open, from a second connection, I'm going to create a new transaction in which I am going to update this row to set the value it is storing to 1 from 0, and then commit. In the first connection, as we are still in a "snapshot" (I put this term in quotes, as MVCC is obviously not copying the entire database when a transaction begins) from a transaction started before that update, we will not see the update happen, but the hidden xmax column (which stores the transaction in which the row is deleted) will be updated.
Connection 2:
demo=> begin; select txid_current();
BEGIN
189029
demo=> update q set data = 1; commit;
UPDATE 1
COMMIT
demo=> select xmin, xmax, data from q;
189029|0|1
Connection 1:
demo=> select xmin, xmax, data from q;
189028|189029|0
As you can see, the data that the other transaction was referencing has not been destroyed: the old row (the one with the value 0) is still there, but the xmax column has been updated to indicate that this column no longer exists for transactions that began after 189029 committed. However, at the same time, the new row (with the value 1) also exists, with an xmin of 189029: transactions that begin after 189029 committed will see that row instead. No data was destroyed: and this data is persisted this way to disk (it isn't just stored in memory).
My contention then is that it should be a fairly simple matter to take a transaction and backdate when it began. As far as I know, there is no reason that this would cause any serious problems as long as a) it was done before the transaction updated or inserted any data, b) there have been no vacuums during the backdated period, c) HOT (heap-only tuple) updates are disabled (in essence, this is an optimization designed to do online vacuuming), and maybe d) the new transaction is read only (although I am fairly confident this would not be a requirement).
For a more complete implementation, one would then want to be able to build transactions (probably read-only ones; I imagine this would cause serious problems if used from a writable transaction, and that really isn't required) that "saw all data as if all data in the database was alive", which I also believe would be a pretty simple hack: you just take the code that filters dead rows from being visible based on these comparisons and add a transaction feature that lets you turn them off. You could then use the already-implemented xmin and xmax columns to do your historical lookups.
P.S. BTW, if you want to try that demo at home, to get that behavior you need to use the "repeatable read" isolation level, which uses the start of the transaction as the boundary as opposed to the start of the query. This is not the default; you might then wonder if it is because it is expensive and requires a lot more coordination, and as far as I know the answer is "no". In both cases, all of the data is stored and is tagged with the transaction identifiers: the difference is only in what is considered the reference time to use for "which of the rows is alive".
However, it does mean that a transaction that attempts to update a value that has been changed from another transaction will fail, even if the updating transaction had not previously read the state of the value; as most reasonable usages of a database actually work fine with the relaxed semantics that "data truly committed before the query executes" provides (as that still wouldn't allow data you update to be concurrently and conflictingly updated by someone else: their update would block) and those semantics are not subject to "this transaction is impossible" errors.
Both Connections (setup):
demo=> set session characteristics as transaction isolation level repeatable read;
SET