Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize? Suppose I want a strong 20-bit blockcipher.  In other words, I want a function that takes a key (suppose the key is 128 bits), and implements a permutation from 20 bits to 20 bits.  The set of permutations should be close to a randomly-chosen subset of size $2^{128}$ of all $2^{20}!$ permutations on 20 bits.

I don't want you to build a new blockcipher from scratch.  Instead, assume you have a "strong" blockcipher like AES (128-bit blocksize, 128-bit keysize) and use this to build your 20-bit cipher. 

Of course, your construction should be practical (i.e., you should be able to run it in both directions with reasonable amounts of time and memory).
What you're looking for can be done using existing schemes for format preserving encryption (FPE). In general, FPE schemes convert an existing strong algorithm like AES into a block cipher that operates on a set of any size. For instance, FPE can encrypt 15 digit integers to other 15 digit integers (eg for credit card numbers, one of the common reasons for using FPE). Most of these schemes can be easily adapted for the set [0...2^20), usually with no special changes. For further details see this paper or this wikipedia article.

I assume you're aware that any 20 bit block cipher suffers serious intrinsic weaknesses (eg collisions using it in CBC mode) and have a specific reason for needing a 20 bit permutation.