[BETEPAH]

А если на входе все-таки объект, а не массив массивов, то код рони можно немного дополнить:

var obj  = {
    arr1: [
               'a1_val1', 
               'a1_val2'
            ], 
    arr2: [
               'a2_val1', 
               'a2_val2', 
               'a2_val3'
            ]
}
var arr = [];
for (var key in obj) {
	arr.push(obj[key]);
}
function go(b) {
    for (var a = 0; a < b.length - 1; a++) {
        for (var c = [], d = 0 ; d < b[a].length; d++)
            for (var e = 0; e < b[a + 1].length; e++) c.push(b[a][d] + " " + b[a + 1][e]);
        b[a + 1] = c
    }
    return c
};
alert(go(arr).join('\n'))