If Parsoid is to be used for web page views (as opposed to "internal to editors" and "mobile web" or "app" views), it should respect the WP $wgNoFollowLinks configuration option. This may have to be exported in the MW siteinfo if it is not already present.
We already use rel for link type. The proper way to combine rel attributes is by space-separating them:
To determine which link types apply to a link, a, or area element, the element's rel attribute must be split on ASCII whitespace. The resulting tokens are the keywords for the link types that apply to that element.
https://html.spec.whatwg.org/#linkTypes
There are probably CSS selectors in various places which look like a[rel="...."]. These should be changed to a[rel~="..."] (see https://developer.mozilla.org/en-US/docs/Web/CSS/Attribute_selectors ) -- in fact, they should always have been written that way, but it wouldn't have broken before we added nofollow.