How do I get rid of that extra line at the end of my custom algorithmicx block?

I recently faced the same problem, but I came up with the following workaround after looking into the algpseudocode source code:

% Tell algorithmicx not to print an empty line if `noend' option is set 
\makeatletter
\ifthenelse{\equal{\ALG@noend}{t}}%
  {\algtext*{EndOn}}
  {}%
\makeatother

The need for such a fix for each user-defined block can be considered a bug in algpseudocode, in my opinion. Perhaps you should drop the maintainer an email...

---

Edit: In case you decide not to use the noend option, the following definition for your "On" block probably makes more sense.

\algnewcommand\algorithmicon{\textbf{on}}
\algnewcommand\algorithmicfrom{\textbf{from}}
\algblockdefx[ON]{On}{EndOn}[2]
  {\algorithmicon\ #1\ \algorithmicfrom\ #2\ \algorithmicdo}
  {\algorithmicend\ \algorithmicon}

Complete code

\documentclass[a4paper]{report}

\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

% Defines custom \On ... \EndOn block
\algnewcommand\algorithmicon{\textbf{on}}
\algnewcommand\algorithmicfrom{\textbf{from}}
\algblockdefx[ON]{On}{EndOn}[2]
  {\algorithmicon\ #1\ \algorithmicfrom\ #2\ \algorithmicdo}
  {\algorithmicend\ \algorithmicon}

% Tells algorithmicx not to print an empty line if `noend' is set 
\makeatletter
\ifthenelse{\equal{\ALG@noend}{t}}%
  {\algtext*{EndOn}}
  {}%
\makeatother

\begin{document}
  \begin{algorithm}
    \begin{algorithmic}
      \On{$foo$}{$bar$}
        \State baz
      \EndOn
    \end{algorithmic}
  \end{algorithm}
\end{document}