This would have been my first choice since I want to open the new tab using JS anyway, however it doesn't work on those redirected links in the navigation since the href attribute of those is still a local link.
The navigation is created using Markup Simple Navigation. For any reference to an external page, I have a template page-redirect.php, which contains just
<?php
// Internal or external redirects in primary nav
if($page->redirect_url) $session->redirect($page->redirect_url);
This template only has the fields title and redirect_url. So if I had a page /markup/navigation/ with the redirect_url set to
http://processwire.com, the link href in the navigation markup would still be /markup/navigation/. It's redirected after the link is clicked which is why the JS solution won't work.
Can I maybe add code to Markup Simple Navigation's item_tpl using template selectors?