Mistake in First approach: Here you are using existingTasks which i assume list of task. When you use this as Subject__c not in : existingTasks, Soql compiler thinks existingTasks as list of String but it is list of Task. So only you got the error.
Suggestion: After existingTasks query add this.
Set subjectSet = new Set(); for(Task t : existingTasks){ subjectSet.add(t.Subject); }
Set<string> subjectSet = new Set<string>();
for(Task t : existingTasks){
subjectSet.add(t.Subject);
}
Use the new Set in for each loop as
Subject__c NOT IN: subjectSet
Subject__c NOT IN: subjectSet
If you succeed in this, there won't be a need for second approach ;)