Is there any dark magic I can pull off to exchange my black 4s for a white one?
No restocking fee if you got it from apple.Go to the store and try asking. Then be willing to pay the restocking fee.
Other than that? Not much.
If I got it from Apple.com can I still exchange it at an Apple retail store?
If you ordered online you will have to pay the unsubsidized price ($849 for 64gb) then get a refund when they receive the old phone.