Best way to add Foreign Key to massive table?
First of all, depending not just on the number of rows but also on the total size of your table (based on the average row size) , it may not be excessive to create a new Foreign Key. Especially if scheduled properly.  

However, it may well be too heavy a change.  In that case, you could consider creating an Intersection Table like:

CREATE TABLE FlightPair
(
     departurekey INT REFERENCES arrival NULL,
     arrivalkey INT REFERENCES departure NULL
)


This would allow you to incrementally batch the insert of rows into the intersection table a bit at a time, thus keeping the update transactions quite small.  Perhaps insert one day at a time, 10,000 rows at a time, or some other batching method.  Each batch should be a transaction that begins before the insert/update and commits when finished.

That means that the updating of the batches of your choice would be many small transactions instead of one big one.  That would limit the resources needed and, in many cases, would run faster that one big update.

Perhaps having a date included would help to filter the results more effectively.  NULL keys are probably needed for the periods that are incomplete.

What indexes do you currently have?  SQL performance issues often depend on having the indexes properly defined. The columns in the intersection table likewise need to have indexes, as do the departure and arrival tables.