Serial numbers per group of rows for compound key

Don't. It has been tried many times and it's a pain.

Use a plain serial or IDENTITY column:

• Auto increment table column

CREATE TABLE address_history (
  address_history_id serial PRIMARY KEY
, person_id int NOT NULL REFERENCES people(id)
, created_at timestamp NOT NULL DEFAULT current_timestamp
, previous_address text
);

Use the window function row_number() to get serial numbers without gaps per person_id. You could persist a VIEW that you can use as drop-in replacement for your table in queries to have those numbers ready:

CREATE VIEW address_history_nr AS
SELECT *, row_number() OVER (PARTITION BY person_id
                             ORDER BY address_history_id) AS adr_nr
FROM   address_history;

See:

• Gap-less sequence where multiple transactions with multiple tables are involved

Or you might want to ORDER BY something else. Maybe created_at? Better created_at, address_history_id to break possible ties. Related answer:

• Column with alternate serials

Also, the data type you are looking for is timestamp or timestamptz, not datetime in Postgres:

• Ignoring time zones altogether in Rails and PostgreSQL

And you only need to store previous_address (or more details), not address, nor original_address. Both would be redundant in a sane data model.