Most efficient way to iterate over all DOM elements

The Vanilla Javascript way you posted is the fastest. It will be faster than the jQuery solution you posted (See my comment on the question). If you're not removing or adding anything to the DOM in your loop and order of traversal doesn't matter, you can also speed it up ever so slightly by iterating in reverse:

var items = startElem.getElementsByTagName("*");
for (var i = items.length; i--;) {
    //do stuff
}

Edit: check this benchmark to see how much time you can save by using the native code: http://jsben.ch/#/Ro9H6

UPDATE:

Don't use $('body *') to iterate over the elements. It will be much quicker to use $('*') if you go for the JQuery method (see comments for details).

Plain ol' JavaScript is much faster, relatively speaking.

Using a test fiddle, I get about 30ms to process 13000 elements with JQuery, and 8ms to process 23000 elements using JavaScript (both tested on Chrome):

JQuery:      433  elements/ms
JavaScript:  2875 elements/ms

Difference:  664% in favor of plain ol' JavaScript

Note: Unless you have an incredibly large amount of elements on your page, this isn't going to make much of a difference. Also, you probably should time the logic in your loop, as that might be the limiting factor in all this.

Update:

Here is the updated results when considering much more elements (about 6500 per loop), I get about 648000 elements in 1500ms with JQuery, and 658000 elements in 170ms with JavaScript. (both tested on Chrome):

JQuery:      432  elements/ms
JavaScript:  3870 elements/ms

Difference:  895% in favor of plain ol' JavaScript

Looks like JavaScript sped up while JQuery stayed about the same.

It's not a good idea generally but this should work:

function walkDOM(main) {
    var arr = [];
    var loop = function(main) {
        do {
            arr.push(main);
            if(main.hasChildNodes())
                loop(main.firstChild);
        }
        while (main = main.nextSibling);
    }
    loop(main);
    return arr;
}
walkDOM(document.body);

Not including textnodes:

function walkDOM(main) {
    var arr = [];
    var loop = function(main) {
        do {
            if(main.nodeType == 1)
                arr.push(main);
            if(main.hasChildNodes())
                loop(main.firstChild);
        }
        while (main = main.nextSibling);
    }
    loop(main);
    return arr;
}

Edited!