Yes, put 4.05 on usb drive (PS4/UPDATE/PS4UPDATE.PUP) and insert your new HDD in the console, then be sure to not have any DISC inserted and Internet, only the USB DRIVE, and start installing the system again.
Yes you can offcourse. Just download the recovery pup and not the system pup in order to change a hard drive. Its always handy to have a 4.05 pup backup in case of hdd failure or upgrade. In time there will be more and more fake sites who spread 5.xx firmware as 4.05.