This forum thread outlines a basic way to create a .deb package for distribution, and indeed, this does not involve a need for root privileges. I replicate it here with credit to the forum user curvedinfinity, as a very nice illustration of the basics involved.
The checkinstall
tool described in the link you provided is not primarily intended for general .deb package preparation. It is primarily intended to install software you compile yourself in a way that the package manager knows about it. Accordingly, it requires root privileges. The trick used indeed is to create a .deb file specific for your system, and then install that one. The .deb it creates may not be suited for general distribution.
Excerpt from Ubuntuforums by curedfinity:
Decide on the name of your package. Standard debian notation is all lowercase in the following format:
<project>_<major version>.<minor version>-<package revision>
For example, you could name your first package...
helloworld_1.0-1
Create a directory to make your package in. The name should be the same as the package name.
mkdir helloworld_1.0-1
Pretend that the packaging directory is actually the root of the file system. Put the files of your program where they would be installed to on a system.
mkdir helloworld_1.0-1/usr
mkdir helloworld_1.0-1/usr/local
mkdir helloworld_1.0-1/usr/local/bin
cp "~/Projects/Hello World/helloworld" helloworld_1.0-1/usr/local/bin
Now create a special metadata file with which the package manager will install your program...
mkdir helloworld_1.0-1/DEBIAN
gedit helloworld_1.0-1/DEBIAN/control
Put something like this in that file...
Package: helloworld
Version: 1.0-1
Section: base
Priority: optional
Architecture: i386
Depends: libsomethingorrather (>= 1.2.13), anotherDependency (>= 1.2.6)
Maintainer: Your Name <[email protected]>
Description: Hello World
When you need some sunshine, just run this
small program!
(the space before each line in the description is important)
Now, supposing your current directory is the one containing the folder helloworld_1.0-1
, you just need to make the package:
dpkg-deb --build helloworld_1.0-1
And you're done!
End of citation.