Insert Header at HTTP_REQUEST_SEND phase ?

Try wrapping the HTTP::header commands in the clientside command to force evaluation of the commands into the clientside context. This is necessary as HTTP_REQUEST_SEND is a serverside context event:

when HTTP_REQUEST_SEND {
   set http_send_time [clock clicks -milliseconds] 
   clientside {
      HTTP::header insert "X-loadbalancer-timestamp-send" $http_send_time
      log local0.info "Client sent these HTTP headers [HTTP::header names]"   
   }
}

http://devcentral.f5.com/wiki/default.aspx/iRules/http_request_send

Triggered immediately before an HTTP request is sent to the server-side TCP stack. This is a server-side event. Because of that, if you wish to execute commands in a client-side context in this event, you will need to use the clientside command to do so.

http://devcentral.f5.com/wiki/default.aspx/iRules/clientside

Causes the specified iRule commands to be evaluated under the client-side context.

Aaron