What would happen if you send bitcoins to a non-existent Bitcoin address? If one were to send bitcoins to an address that has not been created yet, what would happen? Would the coins be lost forever? Would they just sit there until the address and key pair are generated?
There's no such thing as a "non-existent" address.  

Other than valid addresses created by a client in which the private key is kept secret there are also are:


Invalid addresses (which will fail the client's sanity checks and thus cannot be used when building a transaction) 
There are also valid addresses in which no key exists.  The private key is required to spend the funds.  If the private key was lost or one was never generated (such as for 1BitcoinEaterAddressDontSendf59kuE) any amounts sent to that address are lost and can never be spent.  There is no way to know if a private key exists for 1BitcoinEaterAddressDontSendf59kuE or if it was a purposely created throw-away address.
There are also valid addresses in which no key can exist.  An answer to a related question provides an example.


There is no way to know for sure that a valid address has no private key.  What is known is that a program like VanityGen would not be able to create an address that includes many readable words like the address 1BitcoinEaterAddressDontSendf59kuE contains using the type of computational capacity that exists today.  So it can be assumed beyond any realm of possibility (but not absolutely, positively 100% guaranteed) that bitcoins sent to that address are gone for good.

Related:


Can a bitcoin be destroyed?
How to generate a valid bitcoin address for destroying bitcoins?