Several lines of evidence suggest that magnetic fields grow rapidly in protogalactic and galactic environments. However, mean field dynamo theory has always suggested that the magnetic fields grow rather slowly, taking of order a Hubble time to reach observed values. The theoretical difficulties only become worse when the system has a high magnetic Reynolds number, as is the case for galactic and protogalactic environments. The discrepancy can be reconciled if fast processes for amplifying magnetic field could operate. Following Balsara, Benjamin & Cox (2001), we show that an interstellar medium that is dominated by realistic energy input from supernova explosions will naturally become a strongly turbulent medium with large positive and negative values of the kinetic helicity. Even though the medium is driven by compressible motions, the kinetic energy in this high Mach number flow is mainly concentrated in solenoidal rather than compressible motions. These results stem from the interaction of strong shocks with each other and with the interstellar turbulence they self-consistently generate in our model. Moreover, this interaction also generates large kinetic helicities of either sign. The turbulent flow that we model has two other characteristics of a fast dynamo: magnetic energy growth independent of scale, and with a growth time that is comparable to the eddy turn-over time. This linear phase of growth permits the field to grow rapidly until the magnetic energy reaches about 1% of the kinetic energy. At that stage, other astrophysical processes for producing magnetic fields can take over. Energetics, power spectra, statistics and structures of the turbulent flow are studied here. Shock-turbulence interaction is shown to be a very general mechanism for helicity generation and magnetic field amplification with applicability to damped Ly-a systems, protogalaxies, the Galaxy, starburst galaxies, the inter-cluster medium and molecular clouds.