Is relationships scalable?
As the site the content differs for each users, it can't be cached.


Well, that is not entirely true. At least for Drupal 8 the options for caching have improved drastically. Previously we could cache a query and its output, but Drupal 8 comes with tag-based caching. 

Every entity in the system can (and core entities by default) expose a cache tag. This allows individual entities to be cached. Views tag-based caching in turn uses these tags to determine if the cached view output can be served or should be rebuilt. 

This means that the view query will still be executed, but all the individual nodes can be served from their individual caches. If none of the nodes has been updated, the rendered output of the view will be served from cache too.

As for scalability (SQL vs NoSQL is not really a Drupal question), there is a tradeoff (but I really do not know enough of this to provide a good explanation). A views relationship is nothing more than an SQL join, this means that all data exists once and is merged into a data set on request. If you do not want to use relationships but a search_api based approach, the same data set should be composed elsewhere. Since you do not want to use relations you should fetch all nodes of all followed users in one run. 

Depending on how your view and search database are configured, this could result in every node getting stored once in the dataset of every follower. With a lot of users and a lot of content this can grow in size very fast. It will likely be faster though because you'll only have to lookup one id instead of all the id's of the entities on the joined tables. 

TL;DR
It depends on what you show and how you build the index.