Well, if you're not doing any network traffic, do a tcpdump -i eth0 ( assuming that's your outbound net connection ). That will tell you what's going on and where.
Another thing to do is to go get chkrootkit (
http://www.chkrootkit.org/ ) and check that out too.
The root password. If it's been changed you'll have to boot off of an install CD, mount the / partiton and edit your passwd file directly. From there change the hash of the password and reboot. However, that probably won't stop whoever it is from coming back in again, so in order to maintain some type of root privelege, make sure you have sudo installed.
From there it's all a matter of checking all of your files to see what's been chagned/added. Usually you'll find directories with a . prefix, so a regular ls -l won't show it. Likewise, you may also see directories labeled ".. " that's two periods and a space, you may just glance right over that and not see it for what it is.
It's a good bet that the majority of your log files have been changed already, however, if you wanted to play the waiting game, you could always upgrade your syslog functioning so that everything is recorded and then push those logs somewhere else, or use virtual terms to tail -f the log files, etc...but that's not a guarntee.
Anyway, hopef I gave you a good starting point for some of the things you've asked.
