RedHat uses a utility called "sulogin" to accomplish this. Booting into single-user mode causes sulogin to run; sulogin prompts for the root password before allowing the user to login.
However, this is easily defeated using "linux init=/bin/sh" instead of "linux single". In order to keep someone with physical access to the box from breaking in, you would need a password-protected boot loader on a system with no CD or floppy drive.
Note that very few services are started when a system isbooted into single-user mode. It occurs to me that perhaps what you really want is multi-user mode with text-only logins, not single-user mode. On RedHat and variants, this is runlevel 3. (Select it with "linux 3" at the lilo prompt, or by specifying "3" in the initdefault line of /etc/inittab.)