Anchors/coordinates inside a node's text

The matrix is imho the best solution. If you don't want all lines crampled, why did you put node={inner sep=0pt}? Removing this option gives:

As the OP noted in a comment, the above solution produces more padding than the standard rectangle solution. This can be avoided by giving inner sep=0pt to the outer matrix node, and inner sep=3.333pt (which is the default inner sep) to each of the inner nodes (cells). There is a MWE which includes the rectangle for comparison:

\usetikzlibrary{positioning, matrix}
\def\legendlines#1#2{
  \draw (#1) -- (#2);
  \draw (#2.north west) -- (#2.south west);
}
\tikzset{
  mynode/.style={draw,fill=blue!30,align=center},
  mylegend/.style={align=left, font=\scriptsize, inner sep=1pt}
}

% Using a matrix, the inter-line space is wrong. I can add row sep=42pt, but I don't know what is the correct value.
\begin{tikzpicture}
  \node[mynode, inner sep=0pt, matrix of nodes,nodes={inner sep=3.33pt}] (N123) {Node line one\\Node line two\\Node line three\\};
  % Coordinates along the east side of N123
  \coordinate (N1east) at (N123-1-1.east -| N123.east);
  \coordinate (N2east) at (N123-2-1.east -| N123.east);
  \coordinate (N3east) at (N123-3-1.east -| N123.east);
  % Legend texts
  \node[mylegend, right=1.0cm of N1east] (L1) {Legend 1};
  \node[mylegend, right=1.2cm of N2east] (L2) {Legend 2};
  \node[mylegend, right=1.4cm of N3east] (L3) {Legend 3};
  % Legend lines
  \legendlines{N1east}{L1}
  \legendlines{N2east}{L2}
  \legendlines{N3east}{L3}
\end{tikzpicture}

\begin{tikzpicture}
 \node[mynode] (N123) {Node line one\\Node line two\\Node line three};
  \node[mylegend, xshift=1cm, at=(N123.east), anchor=west] (L123) {Legend 1\\Legend 2\\Legend 3};
  \legendlines{N123}{L123}
\end{tikzpicture}

Here's a solution using \subnode from the experimental tikzmark package. "Experimental" in this case means "not yet on CTAN": you need to download it from the TeX-SX Launchpad site. Download the file tikzmark.dtx and run tex tikzmark.dtx (if you run latex or pdflatex it will complain of a missing file - ignore that). Put the resulting files somewhere that tex can find them.

Here's your code with the \subnode last.

\documentclass{article}
%\url{http://tex.stackexchange.com/q/86456/86}
\usepackage{tikz}
\usetikzlibrary{positioning, matrix,tikzmark}
\def\legendlines#1#2{
  \draw (#1) -- (#2);
  \draw (#2.north west) -- (#2.south west);
}
\begin{document}
\tikzset{
  mynode/.style={draw,fill=blue!30,align=center},
  mylegend/.style={align=left, font=\scriptsize, inner sep=1pt}
}
% I can't access the position of each line using a rectangle node
\begin{tikzpicture}
  \node[mynode] (N123) {Node line one\\Node line two\\Node line three};
  \node[mylegend, xshift=1cm, at=(N123.east), anchor=west] (L123) {Legend 1\\Legend 2\\Legend 3};
  \legendlines{N123}{L123}
\end{tikzpicture}

% Using a matrix, the inter-line space is wrong. I can add row sep=42pt, but I don't know what is the correct value.
\begin{tikzpicture}
  \node[mynode, matrix, matrix of nodes, nodes={inner sep=0pt}] (N123) {Node line one\\Node line two\\Node line three\\};
  % Coordinates along the east side of N123
  \coordinate (N1east) at (N123-1-1.east -| N123.east);
  \coordinate (N2east) at (N123-2-1.east -| N123.east);
  \coordinate (N3east) at (N123-3-1.east -| N123.east);
  % Legend texts
  \node[mylegend, right=1.0cm of N1east] (L1) {Legend 1};
  \node[mylegend, right=1.2cm of N2east] (L2) {Legend 2};
  \node[mylegend, right=1.4cm of N3east] (L3) {Legend 3};
  % Legend lines
  \legendlines{N1east}{L1}
  \legendlines{N2east}{L2}
  \legendlines{N3east}{L3}
\end{tikzpicture}

% Using an invisible rule
\begin{tikzpicture}
  \node[mynode, matrix, matrix of nodes, nodes={inner sep=0pt}] (N123) {Node line one\\\rule{0cm}{\baselineskip}Node line two\\\rule{0cm}{\baselineskip}Node line three\\};
  % Coordinates along the east side of N123
  \coordinate (N1east) at (N123-1-1.east -| N123.east);
  \coordinate (N2east) at (N123-2-1.east -| N123.east);
  \coordinate (N3east) at (N123-3-1.east -| N123.east);
  % Legend texts
  \node[mylegend, right=1.0cm of N1east] (L1) {Legend 1};
  \node[mylegend, right=1.2cm of N2east] (L2) {Legend 2};
  \node[mylegend, right=1.4cm of N3east] (L3) {Legend 3};
  % Legend lines
  \legendlines{N1east}{L1}
  \legendlines{N2east}{L2}
  \legendlines{N3east}{L3}
\end{tikzpicture}

\begin{tikzpicture}[remember picture]
  \node[mynode] (N123) {\subnode{mynode-1}{Node line one}\\\subnode{mynode-2}{Node line two}\\\subnode{mynode-3}{Node line three}};
  \coordinate (L123) at=(N123.east);
  \foreach \k in {1,2,3} {
  \node[mylegend,xshift=\k cm,anchor=base west] (L\k) at (mynode-\k.base -| L123) {Legend \k};
  \legendlines{mynode-\k.mid west -| N123.mid east}{L\k}
}
\end{tikzpicture}

\end{document}

This produces: