Google likes to see backlinking patterns that appear natural, and any natural linkbuilding campaign has lots of "nofollow" links.
Also, just because a link has a "nofollow" tag doesn't mean that Google doesn't follow it. I have seen lots of reports that indicate that they do. Their algorithm goes based on what they view as natural authority, nothing more, nothing less.
The best way to use social sites is for branding and direct traffic. I would not recommend asking people for random backlinks because link exchanges and other random links with no surrounding content will be pretty worthless in terms of SEO. Its not a bad idea, but you would want to ask for guest post opportunities where you could send in unique content instead of just asking for links. This will take a little more time, but it will be a lot more valuable.