Titanium backup is the best way to back up all of those things. It DOES require root, though. The only problem I've seen with Titanium is that if you're trying to restore from different versions of Android (i.e. backup was made in 2.1, but you're restoring to 2.2) some of the system settings won't restore and if you try they will give you problems. Appbrain is a good way to backup your apps.
If you are just getting a replacement phone you can do a NAND backup (again requires root) and when you get the replacement you should be able to restore from the backup. I haven't actually read about anyone doing this, but in theory it should work. It would also require you to root your new phone.
Hope this helps.