There's actually a back door method to do it. On the Contacts List page,go to the address bar in Internet Explorer, and append ?toolpaneview=2to the end of the URL, and you'll get a screen to add a web part.