The product I work on includes schema changes (AKA "migrations") nearly ever time we release. Each migration is effectively atomic, which takes a bit of work, since not all of the data subject to migration is in the database (PostgreSQL). We only have two stored procedures, though. In our situation, it's practical to ask customers to do a full database backup prior to an upgrade, though I don't know of cases of customers having to roll back.
A fresh install of our product installs a seed schema and data, and then applies whatever sequence of schema changes is needed to migrate that schema to current. Our seed state reflects the oldest supported version of the product in the field, and moves forward whenever the slowest customers do.
An update of the product just applies whatever schema changes haven't already been applied.
The thorny part of the process is that we can't safely rely on most of our production code to assist in the migrations. Relying on whatever version is installed is problematic, since it doesn't know about the upgrades. Updating the app code first is problematic, since it doesn't know about older versions of the schema. As a result, we write (and test) a lot of one-time migration code.
I don't know how we'd handle having a lot of logic in stored procedures.