Sim, claro, você pode usar o Linux sem acesso à Internet. Por um lado, o Linux surgiu pela primeira vez em 1991, uma época em que a internet estava em sua infância e muito poucas pessoas (se alguma) fora da academia e os militares tinham acesso a ela.
Eu usei o Linux por anos, quando minha única conexão com a Internet era um modem de 14,4 kbit / s, então eu não estava conectado durante a maior parte do tempo em que eu estava usando a máquina. Ainda hoje, o Linux não exige a internet, nenhum sistema operacional o faz.
Quanto a qual distro, eu recomendo escolher uma que seja tão antiga quanto o seu computador ou uma das mais modernas e minimalistas. Como Zelda disse, certifique-se de que você pode instalar a partir do CD, pois o USB e até mesmo o DVD podem ser um problema. De volta a 98-99, eu estava usando o Mandrake (agora Mandriva) e depois mudei para o SuSe (agora openSuse). Eu tinha um desktop KDE perfeitamente decente e tudo mais.
Basicamente, você quer uma versão estável que não requer atualização constante. Então, vá para um dos antigos (você ainda pode encontrar os ISOs antigos online) ou vá para um lançamento do LTS.