Debian (both testing and unstable) have currently KDE 3.3 available, I think. If you insist that you need KDE 3.4, you might want to install Kubuntu.
But I think that your main problem will be if the Debian-based distro of your choice will be Debian-compatible enough to use Debian packages without breaking. I've heard that Mepis, Kanotix and Libranet are pretty much Debian-compatible while Knoppix and many others may cause problems. Kubuntu has its own freezed version of Debian packages but it's not guaranteed that all of them will work. Debian (with the new Sarge installer) is 100% Debian-compatible.
If you think that Debian proper is too difficult for you, I'd personally think Mepis or Kanotix would be the best choice. But, of course, this is only my opinion and it's up to you to decide what you want.