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 > MYSQLDUMP.sql
# REPLAY
pbzip2 -dkc MYSQLDUMP.sql | mysql (...)
time-to-convert = time-to-dump+time-to-restore+misc
an alternate way is: convert everything to myisam -> stop mysql -> move ibdata1 file -> start mysql -> convert everything to innodb. This will allow you to do one database at a time but you know myisam caveats...SHOW TABLE STATUS
? If it is closer to 36G for data+index, then you won't save any disk space by file_per_table.