This workaround is obsolete, build 14342 solves the issue. Please use that build instead. See https://github.com/Microsoft/BashOnWindows/issues/91#issuecomment-218379746

build-zsh.txt

# THIS HAS BECOME OBSOLETE. IN BUILD 14342 THIS IS SOLVED, PLEASE USE THAT BUILD INSTEAD (OR MORE RECENT ONES)
# See https://github.com/Microsoft/BashOnWindows/issues/91#issuecomment-218379746

# Workaround to build ZSH on #BashOnUbuntuOnWindows.
# See https://github.com/Microsoft/BashOnWindows/issues/91#issuecomment-208077623

# RUN EACH LINE INDEPENDENTLY. THIS IS NOT AN AUTOMATIC BASH SCRIPT.

# Install dependencies
apt-get install -y git-core gcc make autoconf yodl libncursesw5-dev texinfo checkinstall

# Clone zsh repo and change to it
git clone https://github.com/zsh-users/zsh.git zsh; cd zsh

# BashOnUbuntuOnWindows installs zsh 5.0.2
# You can use another version as well
ZSH_VERSION=5.0.2
# Go to desired version
git checkout zsh-$ZSH_VERSION

# Make configure
./Util/preconfig

# Options from Ubuntu Zsh package rules file (http://launchpad.net/ubuntu/+source/zsh)
# Updated to zsh 5.0.2 on Trusty Tahr (pre-release)
./configure --prefix=/usr \
            --mandir=/usr/share/man \
            --bindir=/bin \
            --infodir=/usr/share/info \
            --enable-maildir-support \
            --enable-max-jobtable-size=256 \
            --enable-etcdir=/etc/zsh \
            --enable-function-subdirs \
            --enable-site-fndir=/usr/local/share/zsh/site-functions \
            --enable-fndir=/usr/share/zsh/functions \
            --with-tcsetpgrp \
            --with-term-lib="ncursesw tinfo" \
            --enable-cap \
            --enable-pcre \
            --enable-readnullcmd=pager \
            --enable-custom-patchlevel=Debian \
            --enable-additional-fpath=/usr/share/zsh/vendor-functions,/usr/share/zsh/vendor-completions \
            LDFLAGS="-Wl,--as-needed -g -Wl,-Bsymbolic-functions -Wl,-z,relro"

# THIS IS A HACK BUT IT WORKS FOR NOW
# OPEN THE config.h FILE GENERATED BY AUTOCONF
# AND COMMENT OUT OR DELETE THE LINE
#  #define HAVE_WAIT3 1

# Compile
make -j5

# OPTIONAL: test 
# This will fail in many places because zsh doesn't fully work yet
make check

# Install
# NOTE: if you've installed the official zsh from Ubuntu make sure to uninstall it first
checkinstall -y --pkgname=zsh --pkgversion=$ZSH_VERSION --pkglicense=MIT make install install.info 
# It's possible this command finishes with an error: `rm: cannot remove ‘infodir’: Directory not empty`.
# Despite that, zsh is installed (at least in my experience). Comment below if that's not the case.

I was getting errors on the last command. Had to run with sudo, still got the cannot remove... error but zsh is install now.
Thanks for this.

I went to install oh-my-zsh, and received an error that zsh was not installed. Found that there was no entry in /etc/shells. I added /bin/zsh and that resolved the issue. Not sure what else might check /etc/shells in this way but might be worth adding a step here if it could effect others.