Moving to innodb_file_per_table?
You already linked rolando's post on how to do the migration. You can change the setting online to make use of per table files, but this will not fix your huge ibdata file size, even though single files are used afterwards.

To discern the time needed, try doing it on another installation you recreate from your backups. That way you will get reasonable numbers (as long as the systems have similar specs and hardware being used) how long this process will take, also you can try it out before laying hands onto the production system.

If you have hard uptime requirements another way to do this online might be through replication. To create a slave, you have create an initial mysqldump with special parameters, but this shouldn't be a problem since I guess you create your backups via dumps anyway?

When setting up the replication, you can let the slave run with innodb_file_per_table even though the master does not. Once all things are set, put the masters' ip onto the slave.

If all this is not possible due to the lack of hardware, then your system with the harsh uptime requirements was maybe sold too cheaply and you now have the ungrateful job to make something work with risks that should have been adressed in the initial planning by getting an adequate test setup besides your production setup.

For getting your mysqldumps to speed up, try piping them directly into parallel bzip, to get the cores to do more work and save time by reducing the needed disk accesses. Rougly like this:

# DUMP
mysqldump ... | pbzip2 -c &gt; MYSQLDUMP.sql
# REPLAY
pbzip2 -dkc MYSQLDUMP.sql | mysql (...)