Any material with a relative permeability greater than 1 will increase inductance when inserted into a coil.
Note that permeability is a complex number and frequency dependent. The imaginary part of permeability contributes to loss and appears as a resistance, so the addition of some material in the coil may increase inductance and also add resistance. Generally, the real part of permeability of materials decreases with frequency, while the imaginary part increases. Thus at some frequency, the material becomes useless for constructing inductors.
Many magnetic materials are also non-linear. This is because they work by aligning internal magnetic domains within the material with the applied magnetic field of the core. At some magnetic flux density, the domains are all as aligned as they can be, and can become no more aligned, and thus can not respond to increasing magnetic flux density. This is called "core saturation".
Any ferromagnetic material, such as iron, nickel, or cobalt, has a high permeability. Paramagnetic materials, such as liquid oxygen work as well. Generally, anything that will stick to a permanent magnet indicates a high permeability at 0 frequency.
In practice, ordinary lumps of metal do not make good cores for inductors because their real permeability decreases rapidly with frequency, and inserting them into a RF inductor just makes them hot. A resistor is a much simpler and economical way to achieve the same electrical effect.
Powdered iron cores and ferrite cores are two common materials engineered to overcome these effects to produce useful inductors up to 10s or sometimes even 100s of MHz. Beyond those frequencies even these materials become ineffective. Fortunately higher frequencies also tend to require lower inductances, and thus air-core inductors become practical.