A VPS is going to be fairly cheap. Unmanaged VPS hosting is pocket change these days.

Out of curiosity, which distro will you settle with? I would highly recommend CentOS, however I know theres quite a few Debian lovers out there. I wouldnt touch Gentoo as it requires a lot more work to do what you want it to.

Why don't you get lessons with... linuxcommandstrainingvideos.com