This is just terminology, no need to think about it too much as different people classify different areas into different categories. For example a lot of statisticians would consider machine learning to be a sub-area of statistics, people from AI would consider machine learning to be a sub area of AI research, and people working with computer science consider it to be a sub-area of computer science.
With this in mind, the thing to understand is that "Deep Learning" is not a distinct area from "Machine Learning", but a part of it. In the same way that "Building Bridges" is a sub-part of "Mechanics" which is a sub-part of "Physics". With the context of your question - neural networks vs deep neural networks, it is a bit like asking how long bridges are distinct from shorter bridges. Different tools and techniques are involved but the concept is the same.
So, your questions:
1) Neural networks are not different, they just typically have to have more parameters (be "bigger") for them to be labelled "deep" neutral networks.
2) Not necessarily, neural networks themselves, loosely, can be thought of as multiple logistic regressions stacked on top of each other. Any time you create a model and feed its results to another model and then another model, etc, and try to "train" those models together, you can consider such architecture to be "deep".
3) Typically if you will use the term "deep learning" everyone will assume you are talking about neural networks, because that is the current trend and because the term "deep learning" was first applied to neural networks. So if you use any other architecture you will have to specify it to not confuse others.
4) Answered by 2)
Best Answer
This has been researched for 20 years or so, and there are many papers claiming to outperform backpropagation. Xin Yao did a lot of work on this in the 1990s, and Kenneth Stanley created one of the currently most active frameworks, NEAT (NeuroEvolution of Augmenting Topologies (see http://www.cs.ucf.edu/~kstanley/neat.html and http://tech.groups.yahoo.com/group/neat/).
There's a lot of published material on different neuroevolutionary techniques, but these references may be useful in getting a feel for progress over the years: