Ik kwam exact hetzelfde probleem tegen en er was geen eenvoudige oplossing voor <2.4, maar sinds 2.4 de $setOnInsert operator laat je precies dat doen.
db.collection.update( <query>,
{ $setOnInsert: { "firstTime": <TIMESTAMP> } },
{ upsert: true }
)
Zie de 2.4 release-opmerkingen van setOnInsert voor meer info.