Ok, a two parter this evening!

The two Knights on c8 and h1 are of opposite color, but (despite the fact I have limitations here) it is unknown which Knight is which. 

The following is known. Black gave White odds of the Queen's bishop; no knight was captured by a pawn; Black can castle.

Once that is completed, then for Part two: If the Black Bishop moves from h2 and is instead on a2, and the conditions known are instead these: No knight or pawn or promoted piece has been captured by a pawn; no pawn capture has been made in the 1st or 8th row; Black can castle; No odds were given. Now which Knight is which?

I'm going to start with #1 first.

Let's see what we know. The c8 knight must have gotten there either before cxb6 or d7-d6 was played, regardless of its colour. The a1 knight must have gotten there before the g3 pawn arrived there.

We also know that the bishop on H2 must be a promoted piece, because the original bishop has been captured on his home square. White has or had also a promoted piece in play. Since Black's promoted bishop had to capture one piece in order to promote on G1. He can't have captured a pawn or knight or Light sq. bishop, so he must've captured a promoted piece or a rook or a queen.

OMG - over my head. Maybe I'll come back later when it's not so late.

White's promotion must have been on the c-file, and after cxb6 was played. It was, of course, black's h-pawn that promoted on g1.

I want to know something before I continu trying to solve this puzzle. Is the capture in the following sequence a capture by a pawn or a capture by a bishop?

That's a capture by a pawn

I'm not sure, but white might have promoted two pieces. The B6 capture was probably a rook or queen.

That seems correct, looks like there had to be two promoted pieces for white

The Knight on C8 must have come from B6; because the Light sq. bishop first had to get out to be captured on G4. The Knight also had to be there before the capture on B6; unless it is a white knight and it just promoted.

The light squared bishop wasn't captured on g4 - it started the game already off the board (it says in the first post that we know that black gave white queen's bishop's odds).

I thought that meant that White started without a light sq. bishop.

It would mean that if white gave black odds of a light-squared bishop. Because black gave white the odds, black's the one wihtout the bishop

The Knight on C8 can't be white. Because if it was white, it must've come from B6 (, it would've checked the King if it came from D6). Because it would come from B6, it must've been there before white's promotions. But then the knight would be stuck there and white couldn't promote. That's why the knight on C8 isn't white.

The knight moved to C8 after the promotion and must've come from D6. Therefore the knight on C8 is black and the knight on H1 is white.

Nice solution. I'll start looking at part two later.

There must have been a capture on the g-file, and since no promoted piece, knight or pawn have been captured by a pawn, and the fact that the bishop on f8 is trapped, it is a rook that is captured. Now we consider that in order for it to get out a rook or a bishop is captured on b6 and later it is replaced by a promoted piece, and since there isn't an capture made on the 8th rank, the pawn could only promote on c8 or h8, but if the pawn promoted to a rook on h8, there isn’t enough pieces to capture to reach the current position, so it promoted on c8, and it must have promoted to a rook, but then the if bishop would have escaped with d6, making it impossible to even have a knight on c8! So the bishop is captured on its original square, and the one on board is in fact a promoted piece on h1. We then see that since e7, b6 and a7 pawn could not have moved before the knight reach c8, the knight came from d6, still making it a black knight.

EDIT: even though there is a  rook on h8, either the king's or the  queen's, does not contra dict the fact that the QUEEN'S rook escaped via c8, since if it is the king's rook that is captured, the queen's rook is then on h8, which still requires it to escape over the king

EDIT: this is part 2

EDIT: the queen can also be captured at b6, but it is basically the same

MORE ON EDIT: the fcapture on the g-file could not have been a white-square bishop because then d6 must be pushed