I think a custom plugin is going to be the best way to do this.
If the client is adding users from the control panel, they'll either have to put in a dummy email address (username+someUniqueId@domain.com), or you can create a front-end "user management" form for them that fills that in behind the scenes.
Regardless, you'll want to be sure "verify email address" is not enabled for the user at this point.
Then, assuming you'll be providing your own front-end login form for these users, with username/password fields (password not required), you'll want to point the form to your plugin's controller with it's own actionLogin method (very similar to Craft's UsersController->actionLogin), but check to see if password is null and if the username is valid and if the email is in the format of the unique email address that was previous assigned.
If so, prompt for their actual email, then send Craft's activation email and let it go through Craft's usual workflow for setting a password on the user account.