Using a full density matrix formalism we show that for a lifetime broadened four-level scheme with a signal wave gain medium a large nonlinear phase shift can be induced without signal wave slowdown and attenuation. In this system the signal wave acquires a large nonlinear phase shift and travels with superluminal propagation characteristics. This raises the possibility of rapidly responding nonlinear phase shifting and possibly phase gating devices for information science.