Are you using InnoDB? If so, take a look at Percona's xtrabackup tool. Or more specifically, use their innobackupex script which wraps xtrabackup and adds support for also dumping any MyISAM tables among other things.
It can do online backups (zero locking for InnoDB) and the output is a valid mysql data directory you can copy into place to restore generally making restores much faster than restoring a dump.
It also supports streaming the backups to other machines, incremental backups, and is just a very robust and useful tool.
I use it to backup extremely busy databases in the 500GB+ range without any issues at all and very little replication delay even when load is especially fierce.
Here's a sample usage that takes a backup and then applies the logs in the backup to make it viable for restore:
innobackupex /var/backups/db
innobackupex --apply-log --use-memory=1G /var/backups/db
Restoring that backup on a box would then look like this (path of the mysql data directory may vary by distro):
cp -r /var/backups/db /var/lib/mysql/data
chown -R mysql:mysql /var/lib/mysql/data
The Percona documentation for this tool is quite good so you can read more about it there:
http://www.percona.com/doc/percona-xtrabackup/innobackupex/innobackupex_script.html
Whatever you go with be sure to test it, including the restore part!