Is it possible to determine password strength without knowing the password?

I would figure there are two ways they've come up with the information that they drew that conclusion from.

1. They ran the net accounts /domain command on a users computer which dumped the password complexity requirements for your organization (assumes Windows / Active Directory)
2. They successfully brute forced (or guessed) user passwords because they were weak. Recent password dumps like LinkedIn have provided a trove of real-world passwords that pen-testers have been using in the field to try to crack passwords.

Without further information it's hard to say how they've come to that conclusion (we have no idea what the red team did or what was in scope) but those two ways are how I would assume they did it.

Not really.

What a tester may know:

• Password policy: When signing up, or when changing a password, the application may restrict the possible passwords, leading to weak passwords. The password policy may also allow weak passwords, but that would be a separate issue.
• Password length: The tester may have gained information about the password length, for example via blind SQL injection, and may not have bothered to gather the password.
• The password: The tester may have gained access to the passwords, for example via SQL injection or via bruteforcing the login. But these issues should be listed separately as well.

Yes, it is possible.

Windows networks may be vulnerable to Null Session attacks which allow the attacker to enumerate system details:

...gain anonymous access to IPC$. By default, Windows NT family hosts allow anonymous access to system and network information through NetBIOS, so the following can be gleaned:

• User list
• Machine list
• NetBIOS name list
• Share list
• Password policy information
• Group and member list
• Local Security Authority policy information
• Trust information between domains and hosts