Removing Doubles Ruins Mesh of My Character
One of the known limitations of the automatic weighting system in Blender is that it really doesn't like dense meshes, especially ones that aren't really close to the bones or that overlap.

With that in mind there are a couple of things to do when parenting your character to the rig. The last one is what's giving you the trouble, so pay close attention to that.

First, and this is also just a good practice, is to make sure your model is neat, with no messy areas, excessive overlap, etc.

Second, make sure all your bones are placed appropriately. In many cases this will be roughly in the center of the parts of your character.

Third, you want the Armature modifier to be as high on the modifier list as possible for a bunch of reasons (do keep it after the mirror modifier though). One of them is that placing a subdivision surface modifier before it will give it a TON mode geometry to try and weight. More geometry equals more problems when weighting. Plus, when you place the subsurf after the armature, you get the added bonus of some smoothing after deformation instead of before, which gives cleaner results in many cases. One of the steps I took when getting it to parent was to remove the subsurf, parent the character, then re add the modifier back afterwards (note: I did not test to see if this was absolutely necessary, but it can only help).

Fourth, and this is the main issue you were having, is you need to be conscious of the scale of your objects. Your scene was in Blender units (the default, and that's completely fine). Blender units are for all intents and purposes the same as metric units, just with no name. So 1 Blender unit is 1 meter. When modelling in 3d, it's best practice to keep things reasonably sized. Approximately real life is best, or somewhere around there. A typical human sized character would be somewhere a bit under 2 meters. However, your character was only the equivalent of 27 cm high. That's a lot of detail squeezed into a small area. Blender can handle it, but the automatic weight painting really doesn't like that. So, to fix your problem, you will need to scale up your character and the rig. I scaled them by a factor of 50, but you can try less if you like. You can also resize things after you've parented them. After resizing, it's also a good idea to apply the scale (and rotation and location while your at it) so that Blender knows where everything is and how big it is (this can be done with Ctrl+A).

The steps I took when I got your file to work were to place the take the unmodified character you provided, as well as the rig from layer 20 and place them on a separate layer (just to keep things clean, not really necessary though). Then, I removed the subsurf from the character. Then I scaled both objects up by 50 (note you'll have to scale up the eyes and any other parts as well after) and applied the location, scale, and rotation (Tip: when you scale up the eyes and things after, if you apply location first they'll scale the same as the rest of the character). After that, parenting with automatic weights should work. It may take a bit to sort itself out, but it shouldn't fail.