Добавление company_id ко всем моделям - абсолютно верный путь. То, о чем вы говорите, очень трудно управлять в долгосрочной перспективе, и может быть непросто убедиться, что правильное соединение используется для хранения правильных данных.
Несмотря на то, что такое разделение на различия, как это, раздражает, это может быть сделано и доказано за довольно короткий промежуток времени, и после этого все будет легче управлять. С named_scope нетрудно фильтровать, используя такие атрибуты.
Простая альтернатива - это развертывание приложения более одного раза с различным database.yml для каждой компании, где данные изолированы на уровне приложения, а не внутри приложения.
Это было бы легко сделать с помощью Passenger (mod_rails) и небольшого количества сценариев оболочки.