The bootloader needs to be aware of the clock speed. As a result there are 16MHz bootloaders and 8MHz bootloaders (clock speed is a parameter when the bootloader is compiled). Burn the Arduino Pro 8MHz bootloader onto the chip and things should be fine, the UART can be used as normal, up to 57600 baud (115200 is too fast for 8MHz, need 16MHz for that.) Ditto for millis() etc., will work as expected, no adjustments needed on the programmer's part.
So yes, a different bootloader is needed, and the fuses need to be set for an 8MHz clock. The fuses actually set the hardware to operate a certain way, but the software (bootloader or your sketch) needs to be told how fast the hardware is running in order to get timing correct. (This is done via the F_CPU parameter.)