How to query contacts with no cases, opportunities etc

Rather than negating a suite of clauses and joining them with OR, negate each individually and join with AND. You will get the added benefit that your query is much more selective.

List<Contact> records = [
    SELECT Id, Name FROM Contact
    WHERE Memberstatus__c != :AC_Utils.stagePayed
    AND npo02__MembershipEndDate__c < :thirtySixMonthsAgo
    AND npo02__LastCloseDate__c < :thirtySixMonthsAgo
    AND ElectedMember__c = false
    AND Id NOT IN (SELECT ContactId FROM Case)
    AND Id NOT IN (SELECT npsp__Primary_Contact__c FROM Opportunity)
];

Note also that you can just use date literals for date filtering, so you may be able to switch to:

npo02__MembershipEndDate__c < LAST_N_MONTHS:36

Probably group your ids in a set before running the query.

Set<Id> contactIds = new Set<Id>();

contactIds.addAll([SELECT ContactId FROM Case]);
contactIds.addAll([SELECT npsp__Primary_Contact__c FROM Opportunity]);


List<Contact> conQuery = [
        SELECT Id, Name FROM Contact
        WHERE NOT(
            Memberstatus__c = :AC_Utils.stagePayed
            OR npo02__MembershipEndDate__c >= :thirtySixMonthsAgo
            OR npo02__LastCloseDate__c >= :thirtySixMonthsAgo
            OR ElectedMember__c = TRUE
            OR ID IN :contactIds)];

You mentioned that you are using a batch job. Thats quite useful. Assuming your Batch is based on your contact Object.

In the execute method, you will get a List<Contact> scope,

Now run 3 queries to find all the Tasks , Opportunities and Cases associated with the Contact, Create Proper Maps to suit your use case, in the end of the iteration you will have contacts lists which are not associated with any related object, you can delete it.

public void execute(List<Contact> scope, BatchableContext bc){

    Map<Id, Opportunity> contactIdVsOppotunityMap= new Map<Id,Opportunity>();
    for(Opportunity opp : [SELECT Id , Contact__c FROM Opportunity WHERE Contact__c In scope]){
        contactIdVsOppotunityMap.put(opp.Contact__c , opp);
    }



    Map<Id, Case> contactIdVsCaseMap= new Map<Id,Case>();
    for(Case ca : [SELECT Id , Contact__c FROM Case WHERE Contact__c In scope]){
        contactIdVsCaseMap.put(ca.Contact__c , ca);
    }


    List<Contact> unAssociatedContacts = new List<Contact>();

    for(Contact con : scope){

        if(contactIdVsOppotunityMap.containsKey(con.Id)){
            continue;
        }
        if(contactIdVsCaseMap.containsKey(con.Id)){
           continue;
        }
        unAssociatedContacts.add(con);

    }

    delete unAssociatedContacts;
}