This is actually interesting - They will shuffle after the first battle, however because of a little weird quirk with triggered abilities, you actually have to start the second battle first, and complete any hero abilities before Chariot shuffles.
The reason for this is because CoF is a triggered ability (Following a rescue) So it's trigger is met by grapes ending the first battle, but then it has to wait for Grapes to complete before it gets to activate, and Grapes doesn't complete until the new battle starts, at which point chariot shuffles, and your opponent can block.