Let the other webmaster know what page the link is on that you'd like changed, and exactly what to change it to. Make it as easy for them as you can.

If the old link isn't working and the new one is, that would be evidence enough for most webmasters to change the URL in their link.

Or, if you could let them know before the old link actually broke, there should be enough evidence on the old and new versions of the site to show the legitimacy of the request for an update. The name would be different, but other evidence would be consistent like the fact that it's still in the same location, has the same staff, etc.

Don't trust the link: command in Google. Sign up for Webmaster Central to get a better list of inbound links. Also, in Yahoo use the Site Explorer to get all of your inbounds. Then I think the best you can do is ask people to update their links via email ... unfortunately most won't. If I were you I would also contact the search engines directly and tell them what's going on (this would probably do no good normally but if you explain to them that you can't 301 because of EDU domain rules they may help you out).

2. After finding these sites I will need to contact the webmasters of all these sites and ask them to change the link. What would you expect as a webmaster to get in such request that will convince you?

Do you mean convince me that your email is legit and not a link hijacking scheme, or convince me to get off my lazy butt and make the change? For the former, i'd put up a webpage that explains what's changing and add a link to it in your email, and maybe even add a link on your homepage? For the latter, a nice gift in the mail would do it, maybe a new laptop? (just kidding)

But i think that'll be the least of your worries, you'll have a much harder time getting people to change the email addresses in their contact lists.

i would concentrate on saying that the page is moving without a redirect in place.

if you make it clear that it will soon be a completely dead link then most webmasters will change it or remove it, as dead links reflect badly on them to their users.

Thank you all for your advise.
It is not going to be simple and I am sure we will loose quite a few links. When the University changed its name, I argued that the domain name should be left alone uj.edu and aju.edu not much of a difference. I explained what is going to happen but the decision was made.
Moshe