You have mentioned some great options. Each option fulfil a different kind of need and are not directly comparable. Here are some pros and cons of these options:
1 Random unique preselected imagess
Pro: Excellent potential for building a brand identity. Say, your logo is a penguin named tux. Use a set of images showing tux in different poses, outfits, doing activities etc.
Con: Someone has to make those images. You'll rely on an artists and possibly a brand identity manager. Besides, what if users did not like your branding material so much.
2 Unique generated images
Pro: Quick and easy if you can use an off the shelf open source software.
Con: May not be as interesting as the previous option.
3 Gravatar
Pro: The easiest to implement. Minimal effort needed to integrate with your application.
Con: Some users may not have gravatar, you'll end up showing the default image for them. Not so much of an issue unless most of your users are not gravatar users.
4 Avatar from social media connections
Pro: Quick and easy if you can use the right off the shelf software.
Cons: Users may not like to expose their FB/Twitter identity on your site.
5 User uploaded avatar
Pro: Allows your users to have their favourite avatar, your app feel more personalized.
Con: A bit of work on your end to create the upload form, store the image, retrieve the image etc.
6 Selection of images for users to choose
Pro: very similar to the first option, but let the users choose which tux image they like.
Con: Same as the first option.
7 Letting the user combine an avatar from provided elements (face, hair, skin, eyes, nose, mouth, etc.)
Pro: Lets the user engage more with your app.
Con: Quite a bit of work on your end. Besides, depending on the KPIs your team is tracking, there may not be a lot of ROI.
So I would ask myself what are the priorities and how much time/resource can I allocate for this avatar feature in my app?
One extreme would be when the priority is to get a working prototype ASAP. I would go with gravatar in that case. The other extreme would be, to prioritise brand identity. I would go with either 1 or 6 in that case. I see the other options sitting somewhere in between these two extremes. So depending on your priorities and budget, you can also go for a non-extreme option.
