Is there a reliable way to find rootkits on foreign servers quickly without making a memory dump or having installed a tool like samhain before?

Reliable - I think no. The definition of rootkit is that it influence on whole system behavior, so any of system function/application, even written and compiled by yourself cannot be trusted. The reliable way can only be with hardware with read only memory on it procedures, like booting clean system from CD-ROM and then running some anti-rootkit applications. But for example I can imagine that my DVD writer can be affected by some rootkit which change its firmware and that way it will be no longer trusted method.

Generally speaking, the best defense against all kinds of intrusion, including rootkits, is to adopt a policy and practice that is conducive to good security. The number one thing that you can do is monitor your log files. To make the process easier, you can use a program like Logwatch but it is still a good idea to understand and evaluate your logs. Another good idea is to use a HIDS program like Aide, Tripwire, or even a system like Samhain that is designed to alert you whenever something changes on your computer. You also need to make sure your vulnerability exposure is controlled and know what it is. Part of this is keeping your system up to date and adopting sensible settings on any server processes. If you follow these approaches, your ability to detect rootkits and other intrusions will be high and your likelihood of contracting them will be low.