wget -c ftp://ftp.indexdata.dk/pub/yaz/yaz-3.0.26.tar.gz
wget -c ftp://ftp.indexdata.dk/pub/zebra/idzebra-2.0.30.tar.gz

tar xvfz yaz-3.0.26.tar.gz
cd yaz-3.0.26
apt-get install fakeroot debhelper
dpkg-buildpackage -rfakeroot -b #will give you aperl -MCPAN -e 'install Data::ICal' list of packages to install
apt-get install pkg-config libxslt1-dev libreadline5-dev libwrap0-dev libicu36-dev
dpkg-buildpackage -rfakeroot -b
cd .. && apt-get install yaz*.deb

do the same for zebra.

I tried to install as much as possible from the apt packages

apt-get install tcl8.4-dev libbz2-dev
apt-get install liblingua-stem-perl libxml-sax-machines-perl libmarc-record-perl libcgi-session-perl libdate-pcalc-perl libdate-ical-perl libdate-manip-perl liblist-moreutils-perl libmarc-charset-perl libmarc-xml-perl libnet-ldap-server-perl libpdf-report-perl libpdf-reuse-barcode-perl libpoe-perl libxml-csv-perl libtext-csv-perl libtext-iconv-perl libxml-dumper-perl libxml-libxml-common-perl libxml-filter-xslt-perl libxml-rsslite-perl libxml-simple-perl

Install the rest from CPAN:

perl -MCPAN -e 'install Class::Factory::Util'
perl -MCPAN -e 'install Data::ICal'
perl -MCPAN -e 'install Date::Calc'
perl -MCPAN -e 'install HTML::Template::Pro'
apt-get remove libmarc-charset-perl (version mismatch)
perl -MCPAN -e 'install MARC::Charset'
perl -MCPAN -e 'install  MARC::Crosswalk::DublinCore'
perl -MCPAN -e 'install MARC::File::XML'
perl -MCPAN -e 'install Mail::Sendmail'
perl -MCPAN -e 'install Net::Z3950::ZOOM'
perl -MCPAN -e 'install POE'
perl -MCPAN -e 'install Schedule::At'
perl -MCPAN -e 'install Text::CSV'
perl -MCPAN -e 'install Text::CSV_XS'
perl -MCPAN -e 'install Text::Iconv'
perl -MCPAN -e 'install XML::RSS'
perl -MCPAN -e 'install YAML::Syck'
perl -MCPAN -e 'install Biblio::EndnoteStyle'
perl -MCPAN -e 'install Algorithm::CheckDigits' (after running make test)

mysqladmin -u root -p{PASS} create koha
mysql -u root -p{PASS}
mysql> grant all on koha.* to 'kohaadmin'@'localhost' identified by '{KOHAPASS}
';
Query OK, 0 rows affected (0.00 sec)

mysql> flush privileges;
Query OK, 0 rows affected (0.00 sec)

mysql> quit
Bye

perl Makefile.PL
make
make test (revert to install packages if you see any error)
make install

useradd koha

Modify apache config (depends on your config) and restart apache

ln -s {KOHA_DIR}/bin/koha-zebra-ctl.sh /etc/init.d/koha-zebra-daemon
ln -s {KOHA_DIR}/bin/koha-zebraqueue-ctl.sh /etc/init.d/koha-zebraqueue-daemon
update-rc.d koha-zebra-daemon defaults
update-rc.d koha-zebraqueue-daemon defaults

Everything should be ok now and you should be able to start the web based install.