Took the (native-)Boolean-free challenge. Approach shamelessly lifted from the λ-calculus, of course, but still a good exercise.

list-out-of-lambda.js

/************************************
 * List Stuff                       *
 ************************************/

var empty_list = function(selector) {
    return selector(undefined, undefined, tru);
};

var prepend = function(el, list) {
    return function(selector) {
        return selector(el, list, fals);
    };
};

var head = function(list) {
    return list(function(h, t, e) {
        return h;
    });
};

var tail = function(list) {
    return list(function(h, t, e) {
        return t;
    });
};

var is_empty = function(list) {
    return list(function(h, t, e) {
        return e;
    });
};

/************************************
 * Boolean Stuff                    *
 ************************************/

var tru = function(t, f) {
    return t();
};

var fals = function(t, f) {
    return f();
};

var not = function(x) {
    return function(t, f) {
        return x(f, t);
    };
};

var and = function(a, b) {
    return function(t, f) {
        return a(
            function() {
                return b(t, f);
            },
            function() {
                return f();
            });
    };
};

var or = function(a, b) {
    return function(t, f) {
        return a(
            function() {
                return t();
            },
            function() {
                return b(t, f);
            });
    };
};

/************************************
 * More List Stuff                  *
 ************************************/

var map = function(fn, l) {
    return is_empty(l)(
        function() {
            return empty_list;
        },
        function() {
            return prepend(fn(head(l)), map(fn, tail(l)));
        });
};

var filter = function(fn, l) {
    return is_empty(l)(
        function() {
            return empty_list;
        },
        function() {
            return fn(head(l))(
                function() {
                    return prepend(head(l), filter(fn, tail(l)));
                },
                function() {
                    return filter(fn, tail(l));
                });
        });
};

/************************************
 * Nats Stuff                       *
 ************************************/

var zero = empty_list;

var inc = function(n) {
    return prepend(empty_list, n);
};
var dec = function(n) {
    return tail(n);
};

var one = inc(zero);

var is_zero = function(n) {
    return is_empty(n);
};

var add = function(a, b) {
    return is_zero(b)(
        function() {
            return a;
        },
        function() {
            return add(inc(a), dec(b));
        });
};

var sub = function(a, b) {
    return is_zero(b)(
        function() {
            return a;
        },
        function() {
            return add(dec(a), dec(b));
        });
};

var mul = function(a, b) {
    return is_zero(b)(
        function() {
            return zero;
        },
        function() {
            return add(a, mul(a, dec(b)));
        });
};

var pow = function(a, b) {
    return is_zero(b)(
        function() {
            return one;
        },
        function() {
            return mul(a, pow(a, dec(b)));
        });
};

var is_equal = function(n, m) {
    return and(is_zero(n), is_zero(m))(
        function() {
            return tru;
        },
        function() {
            return or(is_zero(n), is_zero(m))(
                function() {
                    return fals;
                },
                function() {
                    return is_equal(dec(n), dec(m));
                });
        });
};

var less_than = function(a, b) {
    return and(is_zero(a), is_zero(b))(
        function() {
            return fals;
        },
        function() {
            return is_zero(a)(
                function() {
                    return tru;
                },
                function() {
                    return is_zero(b)(
                        function() {
                            return fals;
                        },
                        function() {
                            return less_than(dec(a), dec(b));
                        });
                });
        });
};

var greater_than = function(a, b) {
    return less_than(b, a);
};

var div = function(a, b) {
    return less_than(a, b)(
        function() {
            return zero;
        },
        function() {
            return inc(div(sub(a, b), b));
        });
};

var rem = function(a, b) {
    return less_than(a, b)(
        function() {
            return a;
        },
        function() {
            return rem(sub(a, b), b);
        });
};

/************************************
 * More More List Stuff             *
 ************************************/

var nth = function(l, n) {
    return is_zero(n)(
        function() {
            return head(l);
        },
        function() {
            return nth(tail(l), dec(n));
        });
};

var drop = function(l, n) {
    return is_zero(n)(
        function() {
            return l;
        },
        function() {
            return drop(tail(l), dec(n));
        });
};

var take = function(l, n) {
    return is_zero(n)(
        function() {
            return empty_list;
        },
        function() {
            return prepend(head(l), take(tail(l), dec(n)));
        });
};

var slice = function(l, start, end) {
    return take(drop(l, start), sub(end, start));
};

var length = function(l) {
    return is_empty(l)(
        function() {
            return zero;
        },
        function() {
            return inc(length(tail(l)));
        });
};