I agree that the three options you listed are the most common (and achievable).

But there's also an option which is actually a mix of all of the above.
Picture this:

1. You extract a list of the usernames and emails from the old CMS, but you don't import any users into your new CMS yet.

2. At the login, all users are met with a prompt similar to a "forgot password" function. 
After typing their email address (or username), you check that the input exists in the list you exported from the old CMS. If yes, you create a new (deactivated) user account for them. You generate a random password (optionally an activation link) and send it to the corresponding email from the old list.

3. User checks his email and uses the generated password (or activation link) to verify his first-time login. At this point, the user account is activated. (Optionally, allow the user to change his password right away.)

PROS to this approach:
- By purging the user table and requiring users to re-verify, you get rid of abandoned accounts from the old site
- You won't have to maintain a legacy database or authentication mechanisms
- Account security is increased (in theory) as all users are in fact forced to change passwords

CONS to this approach:
- All users have to re-verify (and optionally change to a preferred password), which is a minor annoyance for them
- Your communication regarding the need to re-verify needs to be crystal clear to avoid confusion (or fears of attempted phishing).

There's an old blog post describing a very similar scenario - moving from 4.x to 5 (where EPiServer changed their authentication mechanism, rendering old user accounts non-migratable).

http://labs.episerver.com/en/Blogs/Johano/Dates/2008/10/Silently-migrating-users-from-EPiServer-4x-to-CMS-5/