[SalesForce] updating the child record and linking it to parent

Upsert depends upon the value of External ID fields being unique. If you choose to not make External ID unique, you cannot leverage this feature. This means that you would need to leverage external logic in order to perform the upsert operations. Either clean up your data, or use external logic. One potential solution could be to write a trigger to eliminate a previous External ID matching the record's value when it is inserted or updated; you'll still need to clean up data that existed before this trigger was implemented. Off the top of my head, your trigger might look like this:

trigger clearOldIds on Contact (after insert, after update) {
    Set<String> newIds = new Set<String>(); // All new ID values
    for(Contact record:Trigger.new)
        newIds.add(record.External_Id__c);
    newIds.remove(null); // Ignore blank values
    Contact[] others = [SELECT Id FROM Contact WHERE External_Id__c IN :newIds AND Id NOT IN :Trigger.new];
    for(Contact record:others) // Clear old IDs
        record.External_ID__c = null;
    update others;
}

This would probably work in most cases, but you'll need to clean up your data at least once for this to operate correctly.

Another solution would be to create a service that your external service could consume. Here's a primitive example that would cover this:

global with sharing class SystemUtils {
    global webservice void upsertLast(Contact[] records) {
        Map<String, Id> uniqueValues = new Map<String, Id>();
        Contact[] newRecords = new Contact[0], oldRecords = new Contact[0];
        for(Contact record:records)
            uniqueValues.put(record.External_ID__c,null);
        for(Contact record:[SELECT Id,External_ID__c FROM Contact WHERE External_Id__c IN :uniqueValues.keySet() ORDER BY SystemModStamp ASC])
            uniqueValues.put(record.External_Id__c, record.Id);
        for(Contact record:records)
            record.Id = uniqueValues.get(record.External_Id__c);
        for(Contact record:records)
            (record.Id==null?newRecords:oldRecords).add(record);
        insert newRecords;
        update oldRecords;
    }
}

I haven't implemented error checking, that'd be the last step, but this sort of code would conceivably work assuming there were no errors.

For master details relations we need to pass the reference of object and we cant set the ParentObj__c field as null. Here is example from Apex documentation :

Opportunity newOpportunity = new Opportunity(
    Name='OpportunityWithAccountInsert',
    StageName='Prospecting',
    CloseDate=Date.today().addDays(7));

// Create the parent record reference.
// An account with this external ID value already exists.
// This sObject is used only for foreign key reference
// and doesn't contain any other fields.
Account accountReference = new Account(
    MyExtID__c='SAP111111');                

// Add the nested account sObject to the opportunity.
newOpportunity.Account = accountReference;

// Create the opportunity.
Database.SaveResult results = Database.insert(newOpportunity);

Your code should be something like this:

ParentObj__c parentToClone = [Select id, name,External_Key__c from       
ParentObj__c where id='some id'];
ParentObj__c newParent = parentToClone.clone(false,true);
newParent.External_Key__c = newParent.External_Key__c + '_clone';
system.debug('newParent ++ = '+newParent);

ChildObj__c childToClone = [Select id, name,External_child_Key__c,
ParentObj__r.External_Key__c from ChildObj__c where id='some id'];
ChildObj__c newChild = childToClone.clone(false,true);
newChild.External_child_Key__c =   
//childToClone.External_child_Key__c+'_clone';

newChild.ParentObj__c = newParent; // pass the reference of Parent where external id is already set.

upsert newParent External_Key__c;
upsert newChild External_Child_Key__c;

Ref: https://developer.salesforce.com/docs/atlas.en-us.apexcode.meta/apexcode/langCon_apex_dml_nested_object.htm