Can a self-signed certificate's signature algorithm be changed? I've a large number of self-signed certificates that are currently being used by multiple clients which were signed with the SHA1 ('SHA1WITHRSA' as it appears in the cert) algorithm at the time they were created. 

My boss has asked me to look into 're-signing' these with SHA2 (256) instead rather than re-generate a new key that would then be self-signed with SHA2 as this would be a logistical nightmare. We used to be our own CA, which would've made this possible if all keys were signed by us, but we ceased doing that and just started giving out self-signed certs.

I'm not sure if this is possible.  We can easily get access to the private key(s) on the client sites that were used to generate the original (self) signature, however, since I'm not a crypto expert, I don't know if, once a (public) key is self-signed, whether it is possible to somehow 1) detach that signature and 2) replace it with a newly generated one from the same private key which we have just as it was done the first time the key was generated and signed.

Can someone more versed in crypto shed some light on this?
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.