faça o download do (s) arquivo (s) de pacotes e canalize-os através de algo como:
bzcat Packages.bz2 | egrep '^($|Package:|Version:)'
ou, se um simples grep não for bom o suficiente, use grep-dctrl para extrair as informações que você precisa dos arquivos dos Pacotes baixados.