Is a nuclear bomb possible if we build it out of other fissionable materials? Like Fermium or maybe some other heavier element? Could the explosion be increased in size in this way?

Possibly, if you had macroscopic amounts of it. How much Fermium is available for use? Uranium is used because it's naturally occurring and Plutonium because it can be manufactured. Both isotopes typically used, however, are fissile, which is a more stringent requirement than fissionable.

 

http://en.wikipedia.org/wiki/Fissile#Fissile_vs_fissionable

 

IOW, you want something that easily undergoes fission and produces neutrons when it does. One reason Pu-239 is used is because it has a higher neutron yield than U-235, meaning you can get a smaller volume of it to be critical. It's also easier to produce than U-235, which goes back to the question of how much you have available being important.

Americium is fissionable and has a critical mass.

 

http://en.wikipedia.org/wiki/Americium

 

The isotope 242m1Am (half-life 141 years) has the largest cross sections for absorption of thermal neutrons (5,700 barns),[84] that results in a small critical mass for a sustained nuclear chain reaction. The critical mass for a bare 242m1Am sphere is about 9–14 kg (the uncertainty results from insufficient knowledge of its material properties). It can be lowered to 3–5 kg with a metal reflector and should become even smaller with a water reflector.[85] Such small critical mass is favorable for portable nuclear weapons, but those based on 242m1Am are not known yet, probably because of its scarcity and high price. The critical masses of two other readily available isotopes, 241Am and 243Am, are relatively high – 57.6 to 75.6 kg for 241Am and 209 kg for 243Am.[86] Scarcity and high price yet hinder application of americium as a nuclear fuel in nuclear reactors.[87]

There are proposals of very compact 10-kW high-flux reactors using as little as 20 grams of 242m1Am. Such low-power reactors would be relatively safe to use as neutron sources for radiation therapy in hospitals.[88]