Come faccio a annidare una promessa all'interno di un'altra funzione di promessa in node.js?

Circondando il tutto da una new Promise la chiamata non aiuta a niente. Al suo interno, avresti ancora l'inferno di richiamata. E no, lanciando Promise.resolve() anche una funzione che non restituisce nulla non aiuta.

Dovrai promettere le primitive asincrone, cioè le parti più piccole che sono asincrone. Nel tuo caso, è distance.matrix e connect di mongo +insert :

function getMatrix(m, o, d) {
    return new Promise(function(resolve, reject) {
        m.matrix(o, d, function(err, distances) {
            if (err) reject(err);
            else     resolve(distances);
        });
    });
}

function save(url, store, k) {
// cramming connect+insert in here is not optimal but let's not get into unnecessary detail
    return new Promise(function(resolve, reject) {
        MongoClient.connect(url, function(err, db) {
            if (err)
                reject(err);
            else
                db.collection(k).insert(store, function(err, results) {
                    if (err) reject(err);
                    else     resolve(results);
                    db.close();
                });
        });
    });
}

Ora che li abbiamo, possiamo effettivamente usarli e combinare le nostre promesse in ciò che stai effettivamente cercando:

module.exports = Promise.all(dep.map(function(name) {
    distance.departure_time(name);
    return getMatrix(distance, origins, destinations).then(function(distances) {
        if (!distances) throw new Error('no distances');
        var promises = [];
        if (distances.status == 'OK') {
            for (var i=0; i < origins.length; i++) {
                for (var j = 0; j < destinations.length; j++) {
                    var origin = distances.origin_addresses[i];
                    var destination = distances.destination_addresses[j];
                    if (distances.rows[0].elements[j].status == 'OK') {
                        var duration = distances.rows[i].elements[j].duration_in_traffic.value;
                        var myobj = {
                            destination: destination,
                            departure_time: name,
                            duration: duration
                        };
                        var str = destination.replace(/[,\s]+/g, '');
                        promises.push(save(url, myobj, str));
//                                    ^^^^^^^^^^^^^^^^^^^^^
                    }
                }
            }
        }
        return Promise.all(promises); // now wait for all save results
    });
}));