The bigger the database the more complex it will be to implement schema change while keeping track of transactions that happen while your are transitioning. However I see no reason why it shouldn't be feasible given proper amount of preparation. And if short downtime is a goal I don't see why a proper amount of time developing a solution wouldn't make it either.

And on top of that PostgreSQL community is implementing new way to solve problem with each release. I'm not in a huge live-data use case so I might be wrong, but upcoming logical replication look promising for such use cases https://www.depesz.com/2017/02/07/waiting-for-postgresql-10-....