I'm not aware that there is any version of package.el compatible with 23.4 which supports both multiple archives and the "emacs" pseudo-package.
The problem reported on this thread occurred in the context of a Travis build on 23.4 which used the most recent package.el from the emacs tree known to be compatible with that older Emacs version. The job failure reported that the package emacs-21 was unavailable:
Here's the package.el version in question: http://repo.or.cz/w/emacs.git/blob_plain/ba08b24186711eaeb3748f3d1f23e2c2d9ed0d09:/lisp/emacs-lisp/package.el
It's an unfortunate situation, because we'd either have to backport a better package.el, or we must continue to avoid adding such backwards-incompatible dependencies to the extent we care about 23.x. (package.el already has at least one other unfortunate compatibility quirk, in that recent versions allow the version number to be omitted in Package-Requires headers, while older versions consider that invalid.)