How do I add rel="nofollow" to links in blocks/menus/etc?
I think this is the module you are looking for:

http://drupal.org/project/menu_attributes

With Menu Attributes you can set the rel attribute (among many) on the admin section.