Ya encontre la solucion: basicamente tendria que crear 2 "List", uno de "AUpdatear" y otro de "ABorrar" y cargarlos antes de cualquier accion. Luego recurrir al For each de Baja, hacer SaveChanges, luego el For each de Update, hacer SaveChanges y listo. Recien lo probe y funciona.
List<NombreDelModel> modelAUpdatear = (from s in db.NombreDelModel where s.Id== IdViejo select s).ToList();
List<NombreDelModel> modelABorrar = (from s in db.NombreDelModel where s.Id== Id select s).ToList();
for (var i = 0; i < modelABorrar.Count; i++)
{
db.NombreDelModel.Remove(modelABorrar[i]);
}
db.SaveChanges();
for (var i = 0; i < modelAUpdatear .Count; i++)
{
modelAUpdatear [i].Id = IdNuevo2;
db.NombreDelModel.Add(modelAUpdatear[i]);
}
Tener en cuenta que, en caso de haber relación por primarykey/foreignkey primero se borra desde la última foreign key hacia la primera primary key pero se updatea desde la primera primary key hacia la última foreign key, y obviamente todos los List se cargan al principio, antes de cualquier acción. La verdad es un código interesante, busque en varios sitios y a nadie se le había ocurrido.