Sounds like you have 3 major categories of data you are trying to store:

1. General job data (job id, job requester id, job receiver id etc)
2. State transitions (job started, job finished)
3. State-specific job data
4. (optional) job-related events (price changed, job receiver user reassigned etc)

The key is to separate event-like data from everything else.

Schema design

Here are some details:

1. General jobs table

All of the information that’s NOT state-specific goes into the (let’s say) “jobs” table. Auto-generated primary key: job_id

2. State transitions table

All information about state transitions goes into “job_state_transitions” table, which might have the following columns:

• job_transition_id
• job_id
• created_at
• from_state
• to_state

Ideally this table is append-only. Nothing is every updated or removed here.

Using such a table, you can find out the latest status of any particular job by selecting the latest row for a given job_id from the job_transitions table. You can further denormalize that and introduce a “job_state” column, the contents of which are updated every time a new row is inserted in job_transition table (stored procedures might help here if that’s your thing).

You can also do all sorts of analysis on state transitions, because the timing data is preserved (created_at is a date/time field that can help with that)

3. State-specific job data

All of the state-specific data goes into “[state]-jobs” tables. Primary key: some sequence id. Main index: job_transition_id

4. Optional event data

You can also introduce an “audit trail” table that allows you to keep track of various changes that users might request for each job, like your “change agreed upon price”. This is a generalization of the state transition table: one main table that contains events and a one supplemental table for each event type (for example, price_changes table with job_id, created_at, from_price and to_price columns).

Scaling to millions of users

If the main “jobs” table grows to be unwieldy, you can shard it by job_id or requesting_user_id or something like that.

Likewise, events table should be append-only and can be rotated or purged of events related to jobs that have been finished.

How about a hybrid of the two? A large table with a JobID and state (and perhaps other information common to all jobs and states), with other tables to manage the additional state information. That reduces (or eliminates) the duplication of data, but keeps things more manageable.

You might want to consider using a noSQL database for this specific data.
This way you can just put your object in a record, no matter what the ‘columns’ are.

Depending on the chosen database system (and implemented solution), you would be able to ‘overwrite’ a record with different data if you want. Of course, you can also save your historic data and just PUT a new record in the database.

You can start out with this record:

myStartedObject{
    id: 1,
    state:  'started',
    agreedUponPrice:    100.00,
    someOtherData:  'x'
}

and over time it would change to something like this, or if you want to keep the history records, the id would change.:

myFinishedObject{
    id: 1
    state:  'finished',
    finishedPrice:  209.00,
    someFinishedData:   'y'
}

Storing all state date inside the object is also an option of course, something like this:

myObject
{
    id: 1,
    states: [{ state: 'started', agreedUponPrice: 100.00, someOtherData: 'x'}, 
        { state: 'finished', finishedPrice: 209.00, someFinishedData: 'y'}]
}

Keep in mind, this surely isn’t the silver bullet, but it might be something to consider as you state your ‘schema’ is quite loose and you don’t want to pollute your RDBMS with all of those columns.

Also keep in mind, any RDBMS can do this also. I know in MS SQL you have the XML data type. With this, you can store your data in this XML column. This XML column can contain your deserialized object for instance.
It’s not a ‘real’ noSQL solution, but it looks a bit like one.

If you treat this problem as a workflow problem, you can employ one of the workflow tools such as jBPM or Windows Workflow Foundation and focus on the business logic and let the tool handle the persistence for you.