If you are testing in an older version of Firefox:
Possibly, the reason why your code is not working is because you are testing in a Firefox version earlier than 49.0a (which is currently in beta). In versions before 49.0a, using window.alert() will result in an error. Starting from Firefox version 49.0a, alert() no longer throws an error but instead opens the Browser Console and displays the following message along with your intended text:

alert() is not supported in background windows; please use console.log instead.

In pre-49.0a versions of Firefox, when trying to alert(), you may encounter these errors in the Browser Console:

NS_ERROR_NOT_AVAILABLE: Component returned failure code: 0x80040111 (NS_ERROR_NOT_AVAILABLE) [nsIDOMWindowUtils.isParentWindowMainWidgetVisible]                   nsPrompter.js:346
uncaught exception: unknown (can't convert to string)                                                                                                              (unknown)

Specifically, if you are using alert() in your webRequest listener, the error message would be slightly different:

NS_ERROR_NOT_AVAILABLE: Component returned failure code: 0x80040111 (NS_ERROR_NOT_AVAILABLE) [nsIDOMWindowUtils.isParentWindowMainWidgetVisible]                                                                                                                                                                 nsPrompter.js:346
[Exception... "Component returned failure code: 0x80040111 (NS_ERROR_NOT_AVAILABLE) [nsIDOMWindowUtils.isParentWindowMainWidgetVisible]"  nsresult: "0x80040111 (NS_ERROR_NOT_AVAILABLE)"  location: "JS frame :: resource://gre/components/nsPrompter.js :: openModalWindow :: line 346"  data: no]             (unknown)

Your original code functions correctly:
Your code seems appropriate as per the original question. However, when outputting the new cookie value using console.log(), it doesn't confirm whether the request headers were actually changed. To verify this, you should add another listener for the next event in the chain, webRequest.onSendHeaders.

Below is some adjusted code that ensures the cookie header has been altered, tested on FF48.0.2+:

manifest.json:

{
    "description": "Demonstrate changing the cookie of a WebRequest",
    "manifest_version": 2,
    "name": "change-webrequest-cookie-demo",
    "version": "0.1",

    "permissions": [
        "webRequest",
        "webRequestBlocking",
        "<all_urls>" //Required for Google Chrome. Not, currently, needed for Firefox.
    ],

    "background": {
        "scripts": ["background.js"]
    }
}

background.json:

/*Demonstrate changing the cookie of a WebRequet */
// For testing, open the Browser Console
try{
    //Alert is not supported in Firefox. In in FF49.0+, forces the Browser Console open.
    alert('Open the Browser Console.');
}catch(e){
    //alert throws an error in Firefox versions earlier than 49.0
    console.log('Alert threw an error. Probably, the version of Firefox is less than 49.');
}

chrome.webRequest.onBeforeSendHeaders.addListener(function(details){
  var blockingResponse = {};
  //console.log("Checking headers");
  details.requestHeaders.some(function(header){
      if( header.name == 'Cookie' ) {
          console.log("Original Cookie value:" + header.value);
          header.value = 'twid=notsecret';
          console.log("Cookie Changed");
          return true;
      }
      return false;
  });
  blockingResponse.requestHeaders = details.requestHeaders;
  return blockingResponse;
}, {urls: [ "<all_urls>" ]},['requestHeaders','blocking']);

chrome.webRequest.onSendHeaders.addListener(function(details){
  details.requestHeaders.some(function(header){
      if( header.name == 'Cookie' ) {
          console.log("New Cookie value:" + header.value);
          return true;
      }
      return false;
  });
}, {urls: [ "<all_urls>" ]},['requestHeaders']);

Tips for testing and developing WebExtensions in Firefox

Utilize Firefox Developer Edition or Firefox Nightly:
WebExtensions API continues improving with each Firefox release. It is advisable to develop and test your WebExtension add-on with Firefox Developer Edition or Firefox Nightly. Additionally, make note of the required Firefox version for your desired functionality under the "Browser compatibility" section of MDN documentation pages.

Employ the Browser Console:
Ensure to use the Browser Console to monitor console.log() outputs from your WebExtension background scripts. By checking the Browser Console, you can access error messages which, although require interpretation, provide valuable insights to include in your inquiries.

If you are using the latest versions of Chrome, it is important to include extraHeaders in the options.

As of Chrome 72, certain request headers cannot be modified or removed without specifying 'extraHeaders' in opt_extraInfoSpec

Chrome Developers - chrome.webRequest

For example, if you want to remove Cookies, you can use the following code snippet:

/**
 * Removes cookies 
 */
chrome.webRequest.onBeforeSendHeaders.addListener(function (details) {
  var blockingResponse = {};
  details.requestHeaders.find(a => a.name == "Cookie").value = ``
  blockingResponse.requestHeaders = details.requestHeaders;
  return blockingResponse;
}, { urls: ["<all_urls>"], }, ['requestHeaders', 'extraHeaders', 'blocking', ]);