I've been using zxcvbn to enforce strong passwords for a service where break-ins would cause considerable problems. However, the service is only viable if many users sign up. We've found that users are inclined to walk away in frustration when zxcvbn rejects password after password (based on both website metrics and in-person events). We started with zxcvbn's strength at 4 and have since reduced it to 2, but the problem persists.
It's become painfully clear that your average Jane is used to creating bad passwords and has no interest in being retrained. We don't have the budget to take on responsibility for that kind of social change, and the powers that be are pushing hard to go back to something like "8 characters, at least one number, etc." It's understandable from the business perspective - we spend more time coaching users through the password creation process than we do talking about our service.
So, what's the next best way to enforce a password policy that doesn't leave us with a slew of easily hacked user accounts while at the same time not alienating a non-technical user base?
Edit: Logins happen though web interface as well as others such as IMAP which makes anything other than password-only logins unlikely to be viable.