This method is a bit tedious, but it's not so bad if you put a whole bunch of textures in the same image and do them all together:
Select the entire image. Deselect the first two columns of pixels. Shift down 1 pixel. Deselect the first two columns of pixels of the remaining selection. Shift down 1 pixel. Repeat until you're done.
Make sure you leave space at the bottom of the image so that nothing goes off-canvas.
Deselecting two columns can be done by nudging your selection over two pixels, most editors allow doing this with the keyboard, so it's just a couple of quick taps. You can also save a lot of time by arranging your textures vertically in a narrow image, so there are fewer columns that you have to move.
Photoshop allows skewing at arbitrary angles, so if you have access to it, you could use that. However, the angle you want is arctan(1/2), or about 26.56 degrees, not 22.5.
Edit: The method of shifting the pixels down is trivial to automate. In case none of your programs support scripting, here's a
HTML5 tool that takes an image and skews it using that method. It will not work with very large images due to browser limits on the canvas size, but it'll work with reasonably sized images. It's just a single HTML page with some JavaScript on it, so you can just save the page to use it locally without visiting the website.