Note that this answer is outdated and Sergey Romanovsky gives a much better one. I cannot delete this one because it is marked accepted, but please note it now serves more as a basic illustration of zsh's widget programming.

Custom widget history-incremental-multi-search for zsh

Setup

Create a directory and include it in your $fpath For example, I created a directory ~/.zsh/functions, and the line fpath=($HOME/.zsh/functions $fpath) in my .zshrc.

Put the following in a file named history-incremental-multi-search in that directory.

emulate -L zsh
setopt extended_glob

local oldbuffer=$BUFFER
local -i oldcursor=$CURSOR

local dir                # search direction
local chars              # input buffer
local -a words           # search terms
local -a found           # all history items that match first term
local -i hindex=$HISTNO  # current 
local -i lmatch          # last matched history item (for prev/next)

if [[ $WIDGET == *forward* ]]; then
    dir=fwd
else
    dir=bck
fi

function find-next {
    # split the input buffer on spaces to get search terms
    words=(${(s: :)chars})

    # if we have at least one search term
    if (( $#words )); then
        # get all keys of history items that match the first
        found=(${(k)history[(R)*$words[1]*]})
        if (( $#found )); then
            # search in widget direction by default
            # but accept exception in $1 for "prev match"
            search-${1:-$dir}
        else
            # no matches
            lmatch=$HISTNO
        fi
    else
        # no search terms
        lmatch=$HISTNO
        BUFFER=$oldbuffer
        CURSOR=$oldcursor
    fi
}

function search-fwd {
    # search forward through matches
    local -i i
    for (( i = $#found; i > 0; i-- )); do
        # but not before hindex as we're searching forward
        if [[ $found[$i] -gt $hindex ]]; then
            set-match $found[$i]
        fi
    done
}

function search-bck {
    # search backward through matches
    local -i i
    for (( i = 1; i <= $#found; i++ )); do
        # but not beyond hindex as we're searching backward
        if [[ $found[$i] -lt $hindex ]]; then
            set-match $found[$i]
        fi
    done
}

function set-match {
    # match history item against all terms and select it if successful
    local match=1
    local -i i
    for (( i = 2; i <= $#words; i++ )); do
        if [[ $history[$1] != *$words[$i]* ]]; then
            match=0
            break
        fi
    done
    if [[ $match -ne 0 ]]; then
        lmatch=$1
        BUFFER=$history[$1]
        CURSOR=$#BUFFER
        break
    fi
}

# display sub prompt
zle -R "${dir}-i-search-multi:"

# handle input keys
while read -k; do
    case $REPLY in
        # next
        $'\C-n' )
            hindex=$lmatch
            find-next
            ;;
        # prev
        $'\C-p' )
            hindex=$lmatch
            if [[ $dir == fwd ]]; then
                find-next bck
            else
                find-next fwd
            fi
            ;;
        # break
        $'\e' | $'\C-g' )
            BUFFER=$oldbuffer
            CURSOR=$oldcursor
            break
            ;;
        # accept
        $'\C-m' | $'\C-j' )
            if [[ $lmatch -eq $HISTNO ]]; then
                BUFFER=$oldbuffer
                CURSOR=$oldcursor
            else
                HISTNO=$lmatch
            fi
            break
            ;;
        # erase char
        $'\C-h' | $'\C-?' )
            chars=$chars[1,-2]
            hindex=$HISTNO
            find-next
            ;;
        # erase word
        $'\C-w' )
            if [[ $chars =~ \  ]]; then
                chars=${chars% *}
            else
                chars=
            fi
            hindex=$HISTNO
            find-next
            ;;
        # kill line
        $'\C-u' )
            chars=
            hindex=$HISTNO
            find-next
            ;;
        # add unhandled chars to buffer
        * )
            chars=${chars}${REPLY}
            hindex=$HISTNO
            find-next
            ;;
    esac

    zle -R "${dir}-i-search-multi: $words"
done

Put this in or source it from your .zshrc:

autoload -U history-incremental-multi-search

# make new widgets from function
zle -N history-incremental-multi-search-backward history-incremental-multi-search
zle -N history-incremental-multi-search-forward history-incremental-multi-search

# bind the widgets to keys
bindkey '^Xr' history-incremental-multi-search-backward
bindkey '^Xs' history-incremental-multi-search-forward

Use

You should now be able to initiate a backward incremental search with Ctrl+X, r, forward with Ctrl+X, s.

Type your search terms separated by space. Following keys are available to control it:

• ← Backspace: erase character

• Ctrl+W: erase word

• Ctrl+U: kill line

• Ctrl+N: next match

• Ctrl+P: previous match

• Ctrl+G/Esc: cancel search

• Enter: accept

This solution can probably be simplified quite a bit. It's more a functional proof of concept, with lots of room for improvement.

That, unfortunately, is up to bash, not to the terminal. Your options are:

1. Use semicolons instead of newlines, although even then you can't move up a screen line at a time but must use character or word motion commands. (Oddly, zsh at least lets you move within a compound command when editing history, just not within the current command.) Sometimes fc (which tosses you into your editor with the previous command) is the easiest way to handle compound commands.

2. If you are using Bash, use the following key combination:

   ctrl x e
   

   It will open up the command you are working on using your text editor. Save the file and quit. (I found the command on the Shell Hater's presentation.) Zsh users have this alternative.