Can a self-signed certificate's signature algorithm be changed?
Yes, you can do this, but you would need to change the OID for the signature generation algorithm as well. This may require some more advanced ASN.1 decoding and re-encoding. This is very likely more problematic than the calculation of the signature.

Obviously the fingerprint of the certificate will change as well (as that is just over the binary encoding of the certificate). So beware of this if the certificate is placed in a trust store.