How does recommendation by matrix factorization deal with new movies / users for which there are ratings?
tl;dr:  It can't! 

Why not?

This is one of the main problems of collaborative-filtering recommender systems (i.e. ones that rely solely on the user-item interaction matrix to generate recommendations).

This is referred to as the cold start problem:


  As collaborative filtering methods recommend items based on users' past preferences, new users will need to rate sufficient number of items to enable the system to capture their preferences accurately and thus provides reliable recommendations.
  source


The same is true for new items.

How can we combat this?

The easiest way to combat this issue is to initially identify similar users through demographics and recommending popular items to the user group that best represents him.

Another very popular approach is making a hybrid recommender system, i.e. employs both collaborative-filtering (CF), content-based (CB) and/or even dummy (D) techniques. For instance it could initially recommend the most popular items (D) for new users, then start recommending similar items to the ones he initially liked and finally when the user has rated enough items start looking for users with similar tastes.

In practice most real-world recommender systems are hybrid.


  Netflix is a good example of the use of hybrid recommender systems. The website makes recommendations by comparing the watching and searching habits of similar users (i.e., collaborative filtering) as well as by offering movies that share characteristics with films that a user has rated highly (content-based filtering).
  source