Given, say, the Blowfish block cipher, which is considered secure but only has a 64-bit block size, can we construct a secure block cipher of 128-bit block size?
Say we run the key through two KDFs, and encrypt the first half of the block with the first key, and the second half of the block with the second key. This seems to give a 128-bit block cipher. However, this is probably insecure, since say if we use CTR mode both halves still become insecure by themselves.
One method of doing this would be to construct a Feistel network using the n-bit blockcipher as a round function. A drawback of this approach is that because you're using a blockcipher (a pseudo-random permutation) in place of a pseudo-random function, you are almost immediately limited to being secure to only $q \ll 2^{n/2}$ queries as a result of the Birthday Paradox. For $n = 64$, this could be quite problematic. (And I guess might be the type of scenario that led you to ask this question in the first place).
One way around this is to build a PRF $f_{K_1 K_2}(x) = E_{K_1}(x) \oplus E_{K_2}(x)$, where $E$ is your blockcipher. (See "The Sum of a PRPs is a secure PRF"). This is secure for $q \ll 2^{2n/3}$ queries. The result generalizes to $q \ll 2^{dn/(d+1)}$ when you XOR the outputs of $d$ independently keyed blockciphers. So you could use this for your round function. But since your round functions have to have different keys, you end up using a lot of key material, and there's a significant performance hit.
As an aside, there's a lot of literature on constructing $m$-bit "tweakable" blockciphers out of $n$-bit blockciphers for arbitrary $m > n$. This line of work is motivated mostly by full-disk encryption. See, for example, EME, HEH, HCTR. But almost all of these are again only secure up to $q \ll 2^{n/2}$ queries.
Yes, it should be possible. There are 2 easy ways that I am aware of.
Blowfish is a 64-bit block cipher based on a Feistel structure with a 32-bit F function. This can be extended to a 4 branch design to operate on a 128-bit block quite easily. There would need to be a slight change to the key schedule to distribute the round keys properly, either by performing the key expansion twice on each key half, or by producing more round subkeys. CLEFIA is another block cipher with a 32-bit F function and a 4 branch design, and has been shown to be secure in practice.
The other way is to perform encryption on 64-bit blocks in parallel, and perform some kind of 128-bit mixing operation at regular intervals, such as a large matrix multiplication every 4 rounds. This will redistribute bits between the blocks. Key schedule modification may be necessary to prevent certain undesirable properties when weak keys are used. This method requires a new primitive operation to be used, and that may be infeasible or undesirable.
Additional rounds or slight changes to the key schedule may be required for any form of extension in block size based on a smaller primitive, due to the diffusion rate per round, and how the key schedule is implemented. There are of course more ways to extend the block size, but these 2 have been used in other cipher designs successfully. Other methods may be secure, but with certain limitations.
Other block ciphers that are not based on a Feistel structure require other methods of block size extension. Those methods may have security and performance limitations that can only be overcome by using a cipher designed for the target block size.
