From http://blog.miroslavkoskar.com/2010/11/gnu-readline-vi-mode-visualization-2.html, and for use with a patched readline.

.inputrc_vi_mode_changed

#!/bin/bash

# ... some resources regarding escape sequences ...
# man console_codes
# http://en.wikipedia.org/wiki/ANSI_escape_code
# http://rtfm.etla.org/xterm/ctlseq.html
# http://linuxgazette.net/137/anonymous.html
# http://wiki.archlinux.org/index.php/Color_Bash_Prompt
# http://www.comptechdoc.org/os/linux/howlinuxworks/linux_hlvt100.html
# http://pushpopnil.info/post/804629866/zsh-cursor-color-vi-mode

MODE="$1"
CURSOR_COLOR='\e]12;%s'
HSTATUS="${USER}@${HOSTNAME%%.*}:${PWD/$HOME/~}"

cursor_color() {
    printf "${CURSOR_COLOR}\e\\" "$1"
}

cursor_color_linux() {
    printf '\e[?16;0;%sc' "$1"
}

hstatus() {
    printf '\e]0;%s\e\' "$1"
}

case "${MODE}" in
    'insert')
        if [[ "${TERM}" =~ ^(xterm|rxvt) ]]; then
            cursor_color '#C0C0C0'
            hstatus "[INS] ${HSTATUS}"

        elif [[ "${TERM}" =~ ^screen ]]; then
            hstatus "[INS] ${HSTATUS}"

        elif [[ "${TERM}" =~ ^linux ]]; then
            cursor_color_linux 112

        fi
        ;;
    'command')
        if [[ "${TERM}" =~ ^(xterm|rxvt) ]]; then
            cursor_color 'sienna2'
            hstatus "[CMD] ${HSTATUS}"

        elif [[ "${TERM}" =~ ^screen ]]; then
            hstatus "[CMD] ${HSTATUS}"

        elif [[ "${TERM}" =~ ^linux ]]; then
            cursor_color_linux 64

        fi
        ;;
esac