Cold start recommender system with features I have to develop a recommender system where most of the users only buy 1 item, so I have a cold-start problem. For this reason, I'm discarding matrix factorization techniques and content-based systems in general.
Luckily, I have lots of features for each user. I have the location, age, gender, the device they use to log in, the web browser, mobile carrier, answers to a small login form, among others.
What approaches can I follow given that I have this cold start problem with features?
I understand I can treat it as a multi-class classification problem, where I predict the item that the user is most likely to buy. This has two inconveniences I can think of:

What happens when a new item is added? Do I need to retrain the whole model?
How do I prevent the system from recommending only the most common item? The multi-class problem might give higher probabilities to very common items and my recommendations might get dummy (like recommending bread on a supermarket, doesn't add any value since the user is going to buy it anyway).

Can these issues be solved with a classification approach? Are the other approaches to address these?
Since you have access to user level features, try a k nearest neighbors recommender algo.
When a user signs into your site, find the k most similar looking users (based on a similarity metric such as cosine similarity), and recommend products that those users have purchased.