I'm actually thinking something completely opposite; do we really need to have users input their own password? Why not just generate one for them? Users are notoriously bad at creating passwords (on average), and generating one for them would allow us to throw away all that complex password rule dancing.
For the people that are already using password managers it would be fairly minor change in workflow when creating accounts (which is relatively rare occasion anyways), and for the rest it would be massive improvement in security.