We describe an experimental protocol for introducing spin-dependent lattice structure in a cold atomic fermi gas using lasers. It can be used to realize Hubbard models whose hopping parameters depend on spin and whose interaction strength can be controlled with an external magnetic field. We suggest that exotic superfluidities will arise in this framework. An especially interesting possibility is a class of states that support coexisting superfluid and normal components, even at zero temperature. The quantity of normal component varies with external parameters. We discuss some aspects of the quantum phase transition that arises at the point where it vanishes.