I know there is the Search & Replace functionality built into the control panel but I'm hoping to find a way to do this on all entries and fields without having to run it individually for each field. Has anyone else done this before?
Another option: Low Search has a really nice Find & Replace that allows you to select multiple fields and even restrict by category, a replace preview, and replace log.
As Mark pointed out, you would need to do this in the database. Here's a sample query you could use. MAKE BACKUPS beforehand though!
UPDATE exp_channel_data SET field_id_1 = REPLACE(field_id_1,'string to find','string to replace');
You would need to update the 'field_id_1' with whatever field you're trying to do the find/replace on.