Deferred Name Resolution for Linked Servers
This is most likely not possible. According to the MSDN page for Deferred Name Resolution and Compilation:


  Note
  Deferred name resolution can only be used when you reference nonexistent table objects. All other objects must exist at the time the stored procedure is created. ...


And in fact, over a Linked Server it does not seem that Deferred Name Resolution works at all. I tried (in both SQL Server 2008 R2 RTM and 2012 SP3) with both a Synonym and a direct Linked Server reference to a non-existent Table, and both failed. So it seems that Linked Servers do not support Deferred Name Resolution at all.

However, one thing you might be able to do is to:


Create a single "template" database on the remote server (the DB should have the tables and any other referenced objects created as well)
Create all of the synonyms to point to the template DB
Create the Stored Procedures
DROP and reCREATE the synonyms when the "real" database has been created