The thing you claim works in your question doesn't work:
var main = {
     run: (function()
     {
         var elements = [];
         var allElements = document.querySelectorAll("*");
         for(var i = 0; i < allElements.length; i++)
         {
             if(allElements[i].nodeType != 3)
             {
                 elements.push(allElements[i]);
             }
         }
         for(var i = 0; i < elements.length; i++)
         {
             // Doesn't work
             // this.parseElement(elements[i]);
             // Works 
             main.parseElement(elements[i]);
         }
     })(),
     parseElement: function(e)
     {
         // Unimportant code
     } 
 };
<div></div>
 
 
Fundamentally, you cannot refer to the object being constructed from within the object initializer. You have to create the object first, because during the processing of the initializer, while the object does exist no reference to it is available to your code yet.
From the name run, it seems like you want run to be a method, which it isn't in your code (you've edited the question now to make it one). Just remove the ()() around the function:
var main = {
  run: function() {
    var elements = [];
    var allElements = document.querySelectorAll("*");
    for (var i = 0; i < allElements.length; i++) {
      if (allElements[i].nodeType != 3) {
        elements.push(allElements[i]);
      }
    }
    for (var i = 0; i < elements.length; i++) {
      this.parseElement(elements[i]);
    }
  },
  parseElement: function(e) {
    console.log("Parsing " + e.tagName);
  }
};
main.run();
<div></div>
 
 
Since this is set by how the function is called for normal functions, if you want run to be bound to main so that it doesn't matter how it's called, using main instead of this is the simplest way to do that in that code.
But if you don't want to use main, you could create a bound function:
var main = {
  run: function() {
    var elements = [];
    var allElements = document.querySelectorAll("*");
    for (var i = 0; i < allElements.length; i++) {
      if (allElements[i].nodeType != 3) {
        elements.push(allElements[i]);
      }
    }
    for (var i = 0; i < elements.length; i++) {
      this.parseElement(elements[i]);
    }
  },
  parseElement: function(e) {
    console.log("Parsing " + e.tagName);
  }
};
// Bind run
main.run = main.run.bind(main);
// Use it such that `this` would have been wrong
// if we hadn't bound it:
var f = main.run;
f();
<div></div>
 
 
Just as a side note, we can use Array.prototype.filter and Array.prototype.forEach to make that code a bit more concise:
var main = {
  run: function() {
    var allElements = document.querySelectorAll("*");
    var elements = Array.prototype.filter.call(allElements, function(e) {
      return e.nodeType != 3;
    });
    elements.forEach(this.parseElement, this);
  },
  parseElement: function(e) {
    console.log("Parsing " + e.tagName);
  }
};
// Use it
main.run();
<div></div>
 
 
That assumes that parseElement only ever looks at the first argument it's given (since forEach will call it with three: the entry we're visiting, its index, and the object we're looping through).