[SalesForce] Writing nested custom object records

Yes, you can drive your process from metadata. The key is, as you guessed, in the describe data, specifically, in childRelationships. This will tell you all the objects that have a relationship back to contact. I used Workbench to create this example; I'm pasting in some of the raw JSON that the API returns, but you can map it to what restforce gives you.

/services/data/v32.0/sobjects/Contact/describe

{
  "actionOverrides" : [ ],
  "activateable" : false,
  "childRelationships" : [ {
    "cascadeDelete" : false,
    "childSObject" : "AcceptedEventRelation",
    "deprecatedAndHidden" : false,
    "field" : "RelationId",
    "relationshipName" : "AcceptedEventRelations",
    "restrictedDelete" : false
  }, ...lots more..., {
    "cascadeDelete" : false,
    "childSObject" : "Tweet__c",
    "deprecatedAndHidden" : false,
    "field" : "Contact__c",
    "relationshipName" : "Tweets__r",
    "restrictedDelete" : true
  }, ...lots more..., {
    "cascadeDelete" : false,
    "childSObject" : "Visit_Preparation__c",
    "deprecatedAndHidden" : false,
    "field" : "Contact__c",
    "relationshipName" : "Visit_Preparation__r",
    "restrictedDelete" : false
  } ],
  "compactLayoutable" : true,
  ...
}

You get a whole lot of info back in childRelationships, but you probably want to focus on elements where childSObject has the __c suffix - your custom objects. In my case, these are Tweet__c and Visit_Preparation__c. Now you can build a SOQL query to pull back all the different related records in a single request. For the above example, it is

SELECT Id, Name, 
       (SELECT Id, Name FROM Tweets__r), 
       (SELECT Id, Name FROM Visit_Preparation__r) 
FROM Contact 
WHERE UID__c = 'ID101'

The response looks like

{
  "totalSize" : 1,
  "done" : true,
  "records" : [ {
    "attributes" : {
      "type" : "Contact",
      "url" : "/services/data/v32.0/sobjects/Contact/003E000001CbzBiIAJ"
    },
    "Id" : "003E000001CbzBiIAJ",
    "Name" : "Pat Patterson",
    "Tweets__r" : {
      "totalSize" : 2,
      "done" : true,
      "records" : [ {
        "attributes" : {
          "type" : "Tweet__c",
          "url" : "/services/data/v32.0/sobjects/Tweet__c/a0KE000000CmllPMAR"
        },
        "Id" : "a0KE000000CmllPMAR",
        "Name" : "570319233919422464"
      }, {
        "attributes" : {
          "type" : "Tweet__c",
          "url" : "/services/data/v32.0/sobjects/Tweet__c/a0KE000000Cmm6SMAR"
        },
        "Id" : "a0KE000000Cmm6SMAR",
        "Name" : "570394001620103168"
      } ]
    },
    "Visit_Preparation__r" : {
      "totalSize" : 1,
      "done" : true,
      "records" : [ {
        "attributes" : {
          "type" : "Visit_Preparation__c",
          "url" : "/services/data/v32.0/sobjects/Visit_Preparation__c/a0BE000000SEPpEMAX"
        },
        "Id" : "a0BE000000SEPpEMAX",
        "Name" : "Boondoggle"
      } ]
    }
  } ]
}

A call to the global sobject describe will give you the API name -> Label mapping, so it looks like you can do everything you need with 3 calls, the results of 2 of which (the contact and global describe) are relatively static, so you might be able to cache them.

I think you don't need to pass Parent_Case__r in request.

Salesforce will automatically relate the myrelation__c with case based on the hierarchy that you mentioned in JSON. In your case it will be automatically associated with case name "SampleCase"

if you are trying to relate myrelation__c to any other case record by specifying the Parent_Case__r then it not possible.

Take a look at: https://help.salesforce.com/apex/HTViewSolution?id=000214070&language=en_US

EDIT:

The limitations re documented as:

The request can contain the following:
Up to a total of 200 records across all trees
Up to five records of different types
SObject trees up to five levels deep

https://developer.salesforce.com/docs/atlas.en-us.api_rest.meta/api_rest/resources_composite_sobject_tree.htm