Google says distributing widgets that your users can use on their websites is black hat SEO. How to do it in a white hat way?

Matt Cutts, the head of web spam at Google, made a statement that site owners should nofollow any link on widgets they distribute. So apparently this common practice has also now become gray/black hat tactic.

Is there any way around this to still provide widgets and get both an SEO benefit and provide value from the actual widgets? Without getting penalized by Google, that is.

Make the widget and the link about something the user has created or arranged on your site, instead of every widget having the same link to the root domain. Sites like StackOverflow and Yelp get SEO benefit from users linking back to their profiles on their site, while displaying some of the key info wherever they'd like to embed the widget:

• http://www.yelp.com/bling
• http://stackoverflow.com/users/flair

From Google's point of view, what they care about with widget links (or any kind of link) are things like:

• intent - does the user understand they're linking to the widget provider's site?
• relevancy - is the content and the link within it relevant (e.g. embedding a 'property value calculator' widget shouldn't be giving a 'diet pills' link your site's google juice)
• link profile - if most of a site's google juice is coming from widget links instead of organic linking, that's a signal that the site itself is not actually that valuable, and they'll penalize the links that are boosting it higher than it should be. See also: unnatural links