For changing the hostname without restart use the hostname command:
hostname newhost.domain.com
To keep the new hostname between restarts edit /etc/sysconfig/network, and change the hostname there. (redhat/fedora specific)
Also its a good idea to check /etc/hosts, it can contain the old hostname, change/delete it.