Well this is a very simple process, while Lync has 3 options to display the contact picture, the AD,Mysite and External URL.

Inorder to make the picture available for public contacts, all you need to do is to set Lync to use and External URL which is publicly accessible like Facebook,Photobucket,Linkedin or whatever.

So first upload your image to Publicly Accessible URL and get the direct link till you see the .jpg extension

Then Copy the same Address (Again Make Sure u copy it from the HTTP till the .JPG then insert it into the URL and click connect

If you Get an error that the site requires Username and Password, make sure you can publicly access the URL, or maybe you are sitting behind a TMG.