Sure....a VPS can be completely configured from the command line...no Cpanel needed. I'll warn ye though...it ain't easy.
I would advise most to buy a book first. I'm serious...it's quite a bit of work.
I love my "Linux for Dummies" Book...I use it every day. When I started getting serious with Linux...I didn't want to have to download a distro over dialup (Even though I did end up doing just that...just to see if it could be pulled off) either. The book came with a DVD with Fed 2 on it...which is a very good distro to start with indeed.
I've outgrown it...I use Centos 3.4 and 4 almost exclusively now...
and will have Debian and Gentoo on VPS's shortly as well to round out my inventory.
As far as price...it depends on the host. Sometimes they throw in..say...Cpanel and Fantastico for free...sometimes not.
Most of the VPS's I have you have to pay more for a Cpanel or bring in your own. Some of my VPS's will never have a control panel at all...their purpose is a bit different.