Adding NotNull FK field in existing DB Context:
We’re building a web application to manage business-data. Each “client” of the application has a separate DB (this wont change), and each DB is based off a model (so they are all identical in structure). RDBM is MySQL.

Problem:
When we make modifications to the model DB, we propagate those changes to all client DBs. This is fine in most cases, EXCEPT when we add a new field that is also a not-null FK. In this case the DB upgrade fails.

What we’ve explored:


We could “impose” that all new FK fields can be nullable, however
this potentially defies the business logic that the DB must respect.
We could “select” a default value from the existing data in each
client DB. However, this is potentially absurd: Think of adding a NotNull
FK from Invoice table to Client table… which client should be
selected?


Is there a way to make these types of upgrades without making (crazy) default selections or breaking the business logic of the DB?
It seems that you have run into the reason why NULLs exist in relational databases.  Choosing an arbitrary value from somewhere is a little crazy as you describe.

Options:


Create the needed key (PK or other Unique value) prior to doing the update of the data.  This would require you to pre-decide how to fill each Not NULL FK.  Obviously you want the FK to connect to something or else you would be happy with a NULL.  
Note:I suppose that you could create a row for a default value that joined to each new Not NULL FK that you add. Perhaps give it an ID of -1 and a text of "(Unknown)" or something else that you could work around.  You might wind up scattering around many such "keys" if you are not careful.
Use an Intersection Table instead of adding a foreign key column to the existing table.  The intersection table would consist of two columns: TableAID and TableBID.  In that way, the intersection row will be inserted as needed without any dummy values.  


Sample, from:https://stackoverflow.com/questions/977615/many-to-many-relation-design-intersection-table-design

CREATE TABLE SomeIntersection 
    (TableAID INT REFERENCES TableA NOT NULL,
     TableBID INT REFERENCES TableB NOT NULL,
     PRIMARY KEY(TableAId, TableBId ));