[Crow]

Nicely done, but I still have something for the MS Paint guys that can't afford Photoshop and just want to rotate by 45°.

Note: The hotkeys are for the English version of MS Paint.

1. Obvious step, open MS Paint.
2. Open up the image you want to rotate and select it.
3. Press Ctrl+W to open up the stretch/skew menu and stretch the selected part by 140% vertically and horizontally, basically increasing the size of the image. This has to be done to have the correct size after the rotation.
4. Next step: Important! Deselect first, and reselect the enlarged image! Open up the strech/skew menu again after selecting the image, and skew it horizontally by 45°.
5. Again, deselect the modified image, and reselect it. Stretch/skew menu again, skew vertically by -26°.
6. Almost done! De- and reselect the image again, open up the stretch/skew menu one last time, and stretch your image horizontally by 50%.
7. You are done, congrats :]