First of all, I would recommend providing the data in the form of a table, not as a coordinate list. That makes it a lot easier to manipulate the values, and it allows you to use data from a file. Also, I generally prefer using numeric indices for the x position instead of symbolic x coords. You can use x expr=\coordindex in the \addplot table [...] options to generate these on the fly, and you can use the text from your data as tick labels using the key xticklabels from file. That way, if you decide to change the labels, you only need to alter them at a single location.
If you've read your data table into a macro called \datatable using the \pgfplotstableread command, you can create a new column containing the relative values using
% Get base value
\pgfplotstablegetelem{0}{Value}\of\datatable
% Calculate relative values
\pgfplotstablecreatecol[
create col/expr={
\thisrow{Value}/\pgfplotsretval*100
}
]{Relative}{\datatable}
To make these values available in your nodes near coords in addition to the absolute values, you can use the key visualization depends on=\thisrow{Relative} \as \relativevalue. The values can then be accessed using \relativevalue. Unfortunately, this only works if the plot is created directly from a data file, not from a table macro. The easiest thing to do here is to store the new data table (which contains the new Relative column) into a temporary file, using \pgfplotstablesave[col sep=comma]{\datatable}{temptable.txt} (col sep=comma is necessary because of the spaces in the text labels).
Then you can set your nodes near coords to show both values. I've used siunitx to round and format the numbers:
nodes near coords={%
\pgfmathfloattofixed{\pgfplotspointmeta}%
\num[round-mode=figures, round-precision=2]{\pgfmathresult}\\%
\SI[round-mode=figures, round-precision=2]{\relativevalue}{\percent}%
}
To make the plot start from the y axis, you can set enlarge y limits=upper, ymin=0.
All of that results in the following plot:

\documentclass{article}
\usepackage{pgfplots, pgfplotstable}
\pgfplotsset{compat=1.7}
\usepackage{siunitx}
\begin{document}
\pgfplotstableread{
Name Value
Original 81685
{Linear Traverser} 506326
{MT Linear Traverser} 1754330
{CPU kd-tree} 1873746
{GPU kd-tree} 9023256
}\datatable
% Get base value
\pgfplotstablegetelem{0}{Value}\of\datatable
% Calculate relative values
\pgfplotstablecreatecol[
create col/expr={
\thisrow{Value}/\pgfplotsretval*100
}
]{Relative}{\datatable}
\pgfplotstablesave[col sep=comma]{\datatable}{temptable.txt}
\begin{tikzpicture}
\begin{axis}[
ybar,
scale=0.9,
axis x line= bottom,
axis y line = left,
x post scale = 1.5,
enlargelimits=0.15,
enlarge y limits=upper, ymin=0,
anchor=west,
ylabel=Rays/second,
xticklabels from table={\datatable}{Name},
xtick=data, ytick=\empty,
visualization depends on=\thisrow{Relative}\as\relativevalue,
nodes near coords={%
\pgfmathfloattofixed{\pgfplotspointmeta}%
\num[round-mode=figures, round-precision=2]{\pgfmathresult}\\%
\SI[round-mode=figures, round-precision=2]{\relativevalue}{\percent}%
},
nodes near coords align={vertical},
every node near coord/.append style={align=center},
x tick label style={rotate=45,anchor=east, xshift=-0.1em, yshift=-0.01em},
]
\addplot [fill=gray] table [x expr=\coordindex, col sep=comma] {temptable.txt};
\end{axis}
\end{tikzpicture}
\end{document}