Adding NotNull FK field in existing 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 ));