Old question, new answer suitable for nginx verions 1.3.8, 1.2.5 and above.
You can use a combination of $connection and $connection_requests now.
Just define your own variable in the server block:
server {
    ...
    set  $trace_id  $connection-$connection_requests;
    ...
}
This id is going to be unique across nginx unless the server gets restarted.
$connection - The connection serial number. This is a unique number
  assigned by nginx to each connection. If multiple requests are
  received on a single connection, they will all have the same
  connection serial number. Serial numbers reset when the master nginx
  process is terminated, so they will not be unique over long periods of
  time.
$connection_requests - The number of requests made through this
  $connection.
Then, in your location block, set the actual trace ID:
location / {
    ...
    proxy_set_header X-Request-Id $trace_id;
    ...
}
Bonus: Make $trace_id unique even after server restarts:
set  $trace_id  $connection-$connection_requests-$msec;
$msec - The current unix timestamp in seconds, with millisecond resolution (float).