My goal is to describe my solution strategy in detail, even though my final solution isn't that different from that of @Bass. At multiple points, I will ask a question, which I encourage you to answer on your own before reading further.
So, let's start. The black rook on a1 is the most interesting part of the position. The black rook on h8 is gone and it seems to have done a reverse Houdini to get to a1. So, the first question is
Could the rook from h8 have gotten to a1?
No. Note that a pawn can only be on the 2nd rank if it hasn't been moved. This means that the only way for a rook to pass the second rank is through the opening on h2. But then it would have to pass both the king and rook, neither of which could have moved if white wants to castle. So, then, the next question is
Is there another way for black to get a rook on a1?
Yes. You know the movie, 'The Prestige'? It's a bit like that. You see, the rook on a1 is not the rook from h8, but a body double: the pawn from g7, promoted to a rook. The pawn can pass the 2nd rank by moving across the diagonal. Such a magic trick requires sacrifice, however. Not just from black, who has to give up the rook on h8, but also white, who has to feed the ravenous pawn so that it can move diagonally. But, can white feed enough pieces to the black pawn? First, count how many pieces white can give the black pawn.
How much pieces can white sacrifice?
5. Note that the g7 pawn has to stay on the black diagonal to get it past the pawn chain. This means that we cannot feed it the f1 bishop, as it can't reach the black fields. So, white can easily offer 4 pieces, Queen, Rook, (c1) Bishop and Knight. The final piece is the pawn on h2. This pawn can take the black rook to reach the g line and can promote to Queen on g8 after the g7 pawn has moved to f6, at which point it is easily fed to the pawn.
Is this sacrifice enough?
Yes. While the pawn needs 6 diagonal to promote on a1, the pawn is not promoting to rook on a1, but on b1! This means white can sacrifice the rook on field b2. However, this must be done without checking the king. First, this is the current board:
Now, as white still has its spare bishop, it can be used to shield the king and we can reach the following position:
Almost there, right? Not quite. The problem here is that now the bishop has served its purpose, white will have to get rid of it. To do that, it has to be taken by a black piece. Then, black needs at least one more move to return that piece to its starting position. The problem is that black doesn't have this move, because white's turn is first, and white can only move the rook or king, preventing castle! Is there another way to shield the king from harm?
Can we avoid checking the king?
Yes. The trick is not to use the white f1 bishop, but the black f8 bishop! It takes some maneuvering to get the bishop there, but it works. Before the next part, the white bishop should be cleaned up. We can get to the following position
We are close, but not there yet. The black bishop is one move short of a full retreat, and again white has no moves left. Almost miraculously, there is a way. There is exactly one piece in this position that white could have chosen not to move earlier.
Before reading the final question, I'd like to note that this question is not only the essence of this puzzle (it could have replaced the actual question, in fact), but also one of the key questions of the retrograde-analysis genre. The final question, of course, is:
If white can castle, then what was white's last move?
For the answer I must thank @Bass, because this is where I got stuck. Since I think this is hard, let me give another hint before giving it all away
White has made a move to be able to use a piece it doesn't need to use. It is this move that is white's last move.
And now, the final piece of the puzzle
White's last move is e3!!, allowing the bishop to retreat to f8 and reach the final position, where white may castle. White can afford delaying this move because it doesn't need to use the white bishop, this bishop can be taken on its home square by a black knight.
All in all, an excellent puzzle, not only on a technical level, but also on a psychological one. Why?
One part of the puzzle that struck me was that all pieces sacrificed have been nessecary: reaching this position but with any of them on their home square is impossible. That is, for all but one piece: the f1 bishop. While this bishop is 'dead weight' to reach the end, it is of vital importance for the puzzle. First of all, it makes the solution itself more involved. But more importantly, it creates the deception that moving this bishop is nessecary. This makes finding the solution truly challenging, or as @greenturtle3141 said "The White Bishop covers the King by moving to d1. This fact is undeniable."