- Install Windows Phone 8.1
- Set your theme to sync across devices
- Go to your Windows 8.1 device
- Change the color theme to any color you want
- Go back to your Windows Phone and confirm change.
You may have to wait a few minutes between steps to ensure it takes.
Enjoy!
Edit: I think this works. It may just set the theme color to the closest one on your phone. But when I changed mine to a darker color on my Surface, it also changed the color on my Phone.