Virtual DJ Software for Linux: Mixxx

Mixxx is described as a complete package for amateur and professional DJs alike, providing everything you need to create and perform live mixes. It can run without connecting turntables and mixers, which makes it a replacement for traditional DJ setup. For professionals, it supports advanced features like comprehensive MIDI controller support, vinyl control, and multi-core CPU support.

via Virtual DJ Software for Linux: Mixxx | TechSource.

Seems nice. Packages are available only for Ubuntu, though.