Marcus, the "nofollow" link attribute was originally created to block search engines from following external links to avoid a large amount of spam. But Newsfeed it is not the place where you can see the spam activity. Also, to create oembed links Newsfeed use the oembed third-party library, and adding nofollow attribute to oembed links requires complex code reorganisation. According the reasons mentioned above this is not the major task. But if you need this to be changed, you can implement it by custom code modification.
If you are not familiar with the code modification or plugin development, it would be better for you to find a developer who can help you. You can do it here:
http://www.oxwall.org/market/specialists.