I have found a solution which works in Chrome and Firefox. I've implemented the code in a Userscript, Don't track me Google.
Demo (tested in Firefox 9 and Chrome 17): http://jsfiddle.net/RxHw5/
Referrer hiding for Webkit (Chrome, ..) and Firefox 37+ (33+*)
Webkit-based browsers (such as Chrome, Safari) support <a rel="noreferrer">spec.
Referrer hiding can fully be implemented by combining this method with two event listeners:
mousedown - On click, middle-click, right-click contextmenu, ... 
keydown (Tab Tab Tab ... Enter). 
Code:
function hideRefer(e) {
   var a = e.target;
   // The following line is used to deal with nested elements,
   //  such as: <a href="."> Stack <em>Overflow</em> </a>.
   if (a && a.tagName !== 'A') a = a.parentNode;
   if (a && a.tagName === 'A') {
      a.rel = 'noreferrer';
   }
}
window.addEventListener('mousedown', hideRefer, true);
window.addEventListener('keydown', hideRefer, true);
* rel=noreferrer is supported in Firefox since 33, but support was limited to in-page links. Referrers were still sent when the user opened the tab via the context menu. This bug was fixed in Firefox 37 [bug 1031264].
Referrer hiding for old Firefox versions
Firefox did not support rel="noreferrer" until version 33 `[bug 530396] (or 37, if you wish to hide the referrer for context menus as well).
A data-URI + <meta http-equiv=refresh> can be used to hide the referrer in Firefox (and IE). Implementing this feature is more complicated, but also requires two events:
click - On click, on middle-click, Enter
 
contextmenu - On right-click, Tab Tab ... Contextmenu 
In Firefox, the click event is fired for each mouseup and hitting Enter on a link (or form control). The contextmenu event is required, because the click event fires too late for this case.
Based on data-URIs and split-second time-outs:
When the click event is triggered, the href attribute is temporarily replaced with a data-URI. The event finished, and the default behaviour occurs: Opening the data-URI, dependent on the target attribute and SHIFT/CTRL modifiers.
Meanwhile, the href attribute is restored to its original state.
When the contextmenu event is triggered, the link also changes for a split second.
- The 
Open Link in ... options will open the data-URI. 
- The 
Copy Link location option refers to the restored, original URI. 
- ☹ The 
Bookmark option refers to the data-URI. 
- ☹ 
Save Link as points to the data-URI. 
Code:
// Create a data-URI, redirection by <meta http-equiv=refresh content="0;url=..">
function doNotTrack(url) {
   // As short as possible. " can potentially break the <meta content> attribute,
   // # breaks the data-URI. So, escape both characters.
   var url = url.replace(/"/g,'%22').replace(/#/g,'%23');
   // In case the server does not respond, or if one wants to bookmark the page,
   //  also include an anchor. Strictly, only <meta ... > is needed.
   url = '<title>Redirect</title>'
       + '<a href="' +url+ '" style="color:blue">' +url+ '</a>'
       + '<meta http-equiv=refresh content="0;url=' +url+ '">';
   return 'data:text/html,' + url;
}
function hideRefer(e) {
   var a = e.target;
   if (a && a.tagName !== 'A') a = a.parentNode;
   if (a && a.tagName === 'A') {
      if (e.type == 'contextmenu' || e.button < 2) {
         var realHref = a.href; // Remember original URI
         // Replaces href attribute with data-URI
         a.href = doNotTrack(a.href);
         // Restore the URI, as soon as possible
         setTimeout(function() {a.href = realHref;}, 4);
      }
   }
}
document.addEventListener('click', hideRefer, true);
document.addEventListener('contextmenu', hideRefer, true);
Combining both methods
Unfortunately, there is no straightforward way to feature-detect this feature (let alone account for bugs). So you can either select the relevant code based on navigator.userAgent (i.e. UA-sniffing), or use one of the convoluted detection methods from How can I detect rel="noreferrer" support?.