How can I time-stamp data in MongoDB?
Assuming you are using ObjectIDs for your _id column, then you will already have an insert based timestamp.  You can even extract it from the shell directly if you wish.  Of course, you may want to leave this as-is to permanently store your original insertion timestamp, but adding another would be relatively trivial.  Because most drivers have the ability to generate their own ObjectID and you have the published spec you can easily insert your own with a little research, and in the language of your choice.

Since ObjecIDs are the default _id value, they are also going to be a good choice for indexing, well supported in the drivers etc.

Alternatively, in terms of implementing pure timestamps in MongoDB, there is also a BSON Timestamp data type.  

Storing this (or the aforementioned ObjectID) in a standard field (say "ts" for example) across documents/values would add overhead to a field/doc as you mention, but you should be able to standardize it easily (field.ts would always have a timestamp value) as well as predict the overhead for each field with a timestamp (8 bytes for a timestamp, or 12 bytes for an ObjectID - for more info see bsonspec.org).

Given that you have two native, known datatypes that provide timestamp functionality, they would be my recommendation as a way forward here.

In terms of adding them to existing data, you can choose to "lazily" add them whenever the data is next touched or issue a batch update, depending on your needs - the benefit of a flexible schema.