Here's something like the second option (the node does exist).
There are only two changes to your MWE, in attribute/,style:
The xshift needs adjusting
The anchor point you need can be expressed as an angle
Sorry: I pass on the bonus.
Here it is -- I leave final adjustments to your taste:
\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{trees}
\tikzstyle{every node}=[draw=black,thick,anchor=west, minimum height=2.5em]
\begin{document}
\begin{figure}[!htb]
\resizebox{\linewidth}{!}{
\begin{tikzpicture}[
criteria/.style={text centered, text width=2cm, fill=gray!50},
attribute/.style={%
grow=down, xshift=0cm,
text centered, text width=2cm,
edge from parent path={(\tikzparentnode.225) |- (\tikzchildnode.west)}},
first/.style ={level distance=8ex},
second/.style ={level distance=16ex},
third/.style ={level distance=24ex},
fourth/.style ={level distance=32ex},
fifth/.style ={level distance=40ex},
level 1/.style={sibling distance=10em}]
% Main Goal
\node[anchor=south]{SuperLongTitleWithNoMeaning}
[edge from parent fork down]
% Criteria and Attributes
child{node (crit1) [criteria] {Criteria1}
child[attribute,first] {node {Attribute\\Number1}}
child[attribute,second] {node {Attribute2}}
child[attribute,third] {node {Attribute3}}
child[attribute,fourth] {node {Attribute4}}
child[attribute,fifth] {node {Another\\Attribute}}}
%
child{node [criteria] {Criteria2}
child[attribute,first] {node {Attribute1}}
child[attribute,second] {node {Attribute2}}
child[attribute,third] {node {Third\\Criteria}}
child[attribute,fourth] {node {Longtext-\\criteria}}}
%
child{node [criteria] {Criteria3}
child[attribute,first] {node {Attribute\\two lines}}
child[attribute,second] {node {Attribute2}}
child[attribute,third] {node {Attribute3}}}
%
child{node [criteria] {Criteria4}
child[attribute,first] {node {Attribute1}}
child[attribute,second] {node {Attribute2}}}
%
child{node [criteria] {Criteria5}
child[attribute,first] {node {First\\Attribute}}
child[attribute,second] {node {Attribute2}}
child[attribute,third] {node {Third\\Criteria}}
child[attribute,fourth] {node {Longtext-\\criteria}}};
\end{tikzpicture}}
\caption{This is a nice tree.}
\end{figure}
\end{document}
Tikz builds the tree in such a way that the length level distance is the distance between the point growth parent anchor and the anchor of the child.
By default, the growth parent anchor is center. And the anchor of the children are the default nodes anchors, which are also center. So you get 1cm between the centers of the nodes.
In order to have 1cm between the edges of the nodes as you request, you have to set growth parent anchor to south, and set also the default anchor for all the nodes of the tree to north. The following code implements this idea (and adds some blue lines to test if it works).
\documentclass{article}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[level distance=1cm, growth parent anchor={south}, nodes={anchor=north}]
\path node (a) {a}
child {
node (b) {b}
child {
node [align=center] (cd) {c \\ d}
child {
node (e) {e}
}
}
};
% Testing
\foreach \n in {a,b,cd} {
\draw[blue,<->] (\n.south) ++(2mm,0) -- ++(0, -1cm) node[midway, right]{1cm};
}
\end{tikzpicture}
\end{document}
It works! See the result:
Best Answer
Actually, there are a number of questions with answers which label edges...
This might give you some ideas: