Salvo que quieras hacer algún "hack" , 1 new y un for para hacer otros new es la solución normal.

Otra opción es reservar NxM elementos, y acceder con la fórmula (siendo 'i' el primer índice y 'j' el segundo): matriz[j + i*N]. Teniendo cuidado con matrices especialmente grandes ya que es más probable que obtengas un error al tratar de encontrar NxMx(sizeof) bytes contiguos (cosa más complicada si lo divides en filas).

En cuanto a eficiencia, si bien compiten bastante (y no olvidando que utilizar varios punteros aumenta mucho la legibilidad), se pueden ver pequeños cambios:

#include <ctime>
#include <iostream>
 
using namespace std;
 
template <typename ...Args>
void test(void(*func)(Args...), const char* text, Args... args){
    clock_t cl = clock();
 
    func(args...);
 
    cout << (clock() - cl) << "ms on: " << text << endl;
}
 
int main(){
    const int N = 1000, M = 1000, TIMES = 1000;
 
    int **mat1;
    int *mat2;
 
    test(+[](int*** mat){
        *mat = new int*[N];
        for(int i = 0; i < N; i++){
            (*mat)[i] = new int[M];
        }
    }, "Initialization 1", &mat1);
 
    test(+[](int** mat){
        *mat = new int[N*M];
    }, "Initialization 2", &mat2);
 
 
    test(+[](int** mat){
        for(int l = 0; l < TIMES; l++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    volatile int k = mat[i][j];
                }
            }
        }
    }, "Loop 1 - 1", mat1);
 
        test(+[](int** mat){
            for(int l = 0; l < TIMES; l++){
                for(int i = 0; i < N; i++){
                    for(int j = 0; j < M; j++){
                        volatile int k = mat[j][i];
                    }
                }
            }
        }, "Loop 1 - 2", mat1);
 
    test(+[](int* mat){
        for(int l = 0; l < TIMES; l++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    volatile int k = mat[j + i*N];
                }
            }
        }
    }, "Loop 2", mat2);
}