Forget the .tar.bz2. You want an rpm file. There are dependencies but, go to this site:
http://www.rpmfind.net/linux/RPM/VByName.html
As you can see, I found the page for you -- anyhow, choose a useful rpm and at the command line (and as root) type:
rpm -ivh vlc*
from the directory you downloaded the rpm package to.
If you ARE using an authorized copy of RHEL, by the way, you can just install with "yum install vlc*".
If you are NOT using an authorized copy of RHEL (and can't use yum in other words) I recommend trying either Fedora, which as thhe testing version of RHEL is available freely to testers, or CentOS
http://www.centos.org
which is RHEL with some proprietary images removed --and thus is completely free to use and you can guarantee Red Hat will never call you a pirate or try to sabotage your setup (something I'm told they don't do anyhow but Microsoft and Apple definitely do -- CentOS is distributed under the terms of the license Red Hat uses to distribute many of the packages they do not create. Since even many they do create are released under the same license, CentOS is binary compatible and Red Hat wins by inducing people who wouldn't think they could afford to become developers for them to become developers).
One more page though:
http://www.linuxquestions.org/questions/red-hat-31/video-media-player-mplayer-vlc-in-rhel4-489481/
It's about dependencies for vlc in Red hat. The answer though is either use yum or use rpm -- and the latter does NOT use dependencies. Using the tar.bz2 file means, in essence, recompiling it and it not only won't show up on your menus but will probably crash.