delete records from multiple objects via apex batch class

You can combine up to 10 types of SObject in one list for DML as long as they are grouped by type. See this post by Jesse Altman for more color on that.

You can accomplish what you are looking for by using an Iterable. Take a look here for a good example of how to use an Iterable in a batch (at the bottom). You will want to iterate over a List<SObject>. In your constructor, add your various queries one by one to this list.

Rough example:

global class CustomIterable implements Iterator<SObject>
{
    final List<SObject> records;
    global CustomIterable()
    {
        records = new List<SObject>();
        records.addAll((List<SObject>)[SELECT Id FROM Account]); // WHERE...
        records.addAll((List<SObject>)[SELECT Id FROM Contact]); // WHERE...
        records.addAll(Database.query('SELECT Id FROM Opportunity')); // WHERE...
    }

    // rest of implementation
}

This general approach should get you started.

Here's how I decided to implement my requirement. Still need to test it, but high level seems to be working:

global class DeleteRecords implements Database.Batchable<string>, Database.Stateful  {
global boolean bReRun = false; //will be used to determine if batch has to re-run in case there are more that 10K of records
global Iterable<string> start(Database.BatchableContext ctx) {
    return new list<String> { 'object1', 'object2', 'object3','object4','object5'}; //list of strings with my object names
}
global void execute(Database.BatchableContext ctx, list<string> lstsObjectName) {
    list<sObject> lstDeleteRecords = new list<sObject>();
    for(string strObjectName : lstsObjectName) {
        for(sObject objsObject : database.query('Select Id from ' + strObjectName + ' where for_delete__c = TRUE')) {
            if(lstDeleteRecords.size() < 9998)
                lstDeleteRecords.add(objsObject);
            else {
                bReRun = true;
                break;
            }
        }
    }
    lstDeleteRecords.sort();
    delete lstDeleteRecords;
}
global void finish(Database.BatchableContext ctx) {
    if(bReRun) {
         Database.executebatch(new DeleteRecords());
    }
}

}