Last time I was adding a new record with a reference to a dummy record. I marked the reference as Unchanged so Code First wouldn't try to validate or save it.

var johnCarter = new Movie() { Title = "John Carter" };
johnCarter.DirectorId = andrewStantonId;
context.Movies.Add(johnCarter);
//after it's added, change the status of the reference
context.Entry(johnCarter.Director).State = EntityState.Unchanged;
context.SaveChanges();

Can you set all the references on any entity?

var johnCarter = new Movie() { Title = "John Carter" };
johnCarter.DirectorId = andrewStantonId;
context.Movies.Add(johnCarter);
//after it's added, change the status of the reference
MarkNavigationPropertiesUnchanged(johnCarter);
context.SaveChanges();

We have to look into the underlying EF model.

private static void MarkNavigationPropertiesUnchanged<T>(DbContext context, T entity)
    where T : class
{
    var objectContext = ((IObjectContextAdapter)context).ObjectContext;
    var objectSet = objectContext.CreateObjectSet<T>();
    var elementType = objectSet.EntitySet.ElementType;
    var navigationProperties = elementType.NavigationProperties;
    //the references
    var references = from navigationProperty in navigationProperties
                        let end = navigationProperty.ToEndMember
                        where end.RelationshipMultiplicity == RelationshipMultiplicity.ZeroOrOne ||
                        end.RelationshipMultiplicity == RelationshipMultiplicity.One
                        select navigationProperty.Name;
    //NB: We don't check Collections. EF wants to handle the object graph.
 
    var parentEntityState = context.Entry(entity).State;
    foreach (var navigationProperty in references)
    {
        //if it's modified but not loaded, don't need to touch it
        if (parentEntityState == EntityState.Modified &&
            !context.Entry(entity).Reference(navigationProperty).IsLoaded)
            continue;
        var propertyInfo = typeof(T).GetProperty(navigationProperty);
        var value = propertyInfo.GetValue(entity, null);
        context.Entry(value).State = EntityState.Unchanged;
    }
}

This code only fixes the references to single entities (like movie.Director) - not collections (like director.Movies). It's possible to discover and iterate the collections to change their status, but you'll likely get exceptions from EF because its model is broken.