How to add "rel=nofollow" to ALL external links?
Have you tried this module : Noindex External Links

Module let's you take full control of external links indexing. Pages could also pass HTML-validation.


  Features
  
  Two methods of indexing control:
  
  
  Wrap links with NOINDEX tag. NOINDEX tag is used to deny indexing part of page. Only Yandex and Rambler considers this tag but Google
  and others doesn't. There is also an attribute NOINDEX in meta-tag
  Robots.
  Add attribute rel="nofollow" to links. This link's attribute has no effect on indexing. Only Google really do not follow this links but
  others do. Attribute is used to say to search engine that links no
  longer constitute a "vote" in the PageRank system.