The vertices that tkz-berge draws are regular named TikZ nodes, and so they can be used if one wants unusual edges.

Update: I added four more lines, to show that one can also use the node names provided by tkz-berge, to apply extra labels.

\begin{tikzpicture}
\usetikzlibrary{decorations.pathmorphing,arrows}
\tikzset{EdgeStyle/.append style = {line width=2pt}}
\grEmptyPath[RA=2]{6}
\draw[line width=3pt] (a0) .. controls (-1,1) and (1,1) .. (a0);
\draw[thick,color=blue] (a1) .. controls (0,0) and (2,2) .. (a1);
\draw (a2) .. controls (0,2) and (8,2) .. (a2);
\shadedraw[top color=brown,opacity=0.8] (a3) circle (0.7cm);
\draw[thick,decorate,decoration=snake] (a4) -- (a5);
\draw (a2) node[below]{\textsf{a label}};
\draw (a3) node[above right=5pt]{$v_{0}$};
\node (mytext) at (9,1.5) [shape=rectangle,align=center,draw] {a good\\ vertex};
\draw[->,line width=1pt] (mytext)  -- (a4);
\end{tikzpicture}