Thanks ewcz for your answer, it is a first step toward the expected result. However, as you stated it, this is a little bit trickier to adapt it if you have multiple functions/data to display on the same plot.
Below is a minimal working example with two functions (and thus, two key entries) with a line, points, and points outline of different colors.
# These parameters are used to compute the spacing between entries of the key
pointSize = 1;
yticsScale = 1;
# We use the default spacing (1.25)
keySpacing = pointSize*yticsScale*1.25;
# Initial coordinate of the key
keyY = 4; # In character system
keyX = 0.87; # In graph system
# Just to generate data
set samples 20;
set xrange [-pi:pi];
set term pngcairo;
set output 'graph.png';
set xlabel "x"
set ylabel "y"
# Set the alignment (and thus the coordinate point) of the key
# Set the spacing to -1 to stack different (thanks to ewcz for the idea)
set key bottom right spacing -1
# Start a multiplot
set multiplot
# Make plots as big as possible
set origin 0,0
set size 1,1
# Set the key position
set key at graph keyX, character keyY
# Plot multiple times the same function with different styles.
# Make sure that all functions have a title (empty if necessary).
plot cos(x+pi) w l lc "light-red", \
cos(x+pi) w p pt 5 ps 1.8 lc "dark-red" t ' ', \
cos(x+pi) w p pt 5 ps 1.2 lc "red" t ' '
# Update key coordinates for the next plot
keyY = keyY + keySpacing
# Draw the key of the next plot at the new coordinates
set key at graph keyX, character keyY
plot cos(x) w l lc "light-blue", \
cos(x) w p pt 7 ps 1.8 lc "dark-blue" t ' ', \
cos(x) w p pt 7 ps 1.2 lc "blue" t ' ';
# That's all
unset multiplot
set output;
The resulting plot:

Hope that will help others.
Kind regards.
Alexis
Edit:
The previous code works if both functions/data have the same ranges (on x and y) allowing autoscale to work properly.
In the case of data where you do not know the ranges, you must compute it before plotting.
# Just to generate data
set samples 20;
# First data will be defined on [-pi:pi] with values between -1 and 1.
set table '1.dat'
plot [-pi:pi] cos(x)
unset table
# Second data will be defined on [-pi/2,pi/2] with values between 0 and -2
set table '2.dat'
plot [-pi/2:pi/2] 2*cos(x+pi)
unset table
# These parameters are used to compute the spacing between entries of the key
pointSize = 1;
yticsScale = 1;
keySpacingScale = 1.25; # Gnuplot default spacing
keySpacing = pointSize * yticsScale * keySpacingScale; # Spacing computation
set pointsize pointSize;
set ytics scale yticsScale;
set key spacing -1; # Make key entries overlapping (thanks ewcz for the idea)
# Initial coordinate of the key
keyY = 4.5; # In character system
keyX = 0.98; # In graph system
set term pngcairo;
set output 'graph.png';
# Remove redundant objects
# Borders, labels, tics will be drawn for each plot, this is not necessary as all plots will be stacked. So remove then.
set border 0
set tics textcolor "white" # Dirty tricks to keep plots aligned but to not show the tics
set xlabel " " # The same
set ylabel " " # The same
# Compute the ranges
min(v1, v2) = (v1 < v2) ? v1 : v2;
max(v1, v2) = (v1 > v2) ? v1 : v2;
# Get min and max for the data
stats [*:*] [*:*] '1.dat' name 'f1' nooutput;
stats [*:*] [*:*] '2.dat' name 'f2' nooutput;
# Get the range limits
xmin = min(f1_min_x, f2_min_x)
xmax = max(f1_max_x, f2_max_x)
ymin = min(f1_min_y, f2_min_y)
ymax = max(f1_max_y, f2_max_y)
# Autoscale the range to match all the data
set xrange [* < xmin:xmax < *] writeback
set yrange [* < ymin:ymax < *] writeback
# Start a multiplot
set multiplot
# Make plots as big as possible
set origin 0,0
set size 1,1
# Set the key
set key bottom right at graph keyX, character keyY
# Plot multiple times the same function with different styles.
# Make sure that all functions have a title (empty if necessary).
plot '1.dat' w l lc "light-red" t "cos(x)", \
'' w p pt 5 ps 1.8 lc "dark-red" t ' ', \
'' w p pt 5 ps 1.2 lc "red" t ' '
# Update key coordinates for the next plot
keyY = keyY + keySpacing
# Draw the key of the next plot at the new coordinates
set key at graph keyX, character keyY
# Display at least once the labels
set border
set tics textcolor "black"
set xlabel "x"
set ylabel "y"
# Disable ranges autoscaling
set xrange restore
set yrange restore
plot '2.dat' w l lc "light-blue" t "2cos(x+pi)", \
'' w p pt 5 ps 1.8 lc "dark-blue" t ' ', \
'' w p pt 5 ps 1.2 lc "blue" t ' '
# That's all
unset multiplot
set output;
One more time the resulting plots:

Kind regards,
Alexis