Claim 1: If there are two contiguous groups of coins left of equal size, then the player to move loses.
Proof: If the player makes a certain move in one group, the other player can mimick the same move in the other group. At some point the first player will eliminate one of the groups, at which point the second player can also remove the other group, winning the game.
Claim 2: If there is one (non-cyclic) chain left of any length, then the player to move always wins.
Proof: If there is an even number of coins in the chain, you remove the middle $2$ coins, and Claim 1 then proves the result. Similarly, if there is an odd number of coins, you remove the middle coin, and use Claim 1 to finish the proof.
Claim 3: If there is one cyclic chain left of any length $\geq 3$, then the player to move always loses.
Proof: Removing any number of coins from anywhere in the cycle always leaves a non-cyclic chain of a certain length, allowing the next player to win by Claim 2.
So I think the final answer is that the player to move always loses, unless there are only $1$ or $2$ coins in a "circle".
The usual game of Chomp (with your orientation) has the player eating all cookies that are at least as far right and at least as low down as the selected cookie, not and/or. We can then use strategy stealing on any rectangular board, square or not. The game is a symmetric perfect information game, so every position is either P (won by the previous player) or N (won by the next player). Assume the second player can win, so the rectangle is a P position. The second player must have a winning response to the first player move of the lower right cookie, taking the board to a P position. The first player can make that move (which will include removing the lower right cookie), achieve the P position, then follow the winning second player strategy. This is a contradiction, so our assumption that the second player can win is wrong.
Note that this shows there is a winning first player strategy, but gives no help at finding it. It turns out that on some boards the first player should just take the one cookie, while on others he should take some other move. On square boards, taking just one cookie wins for the first player. He can then make symmetric moves to the second player and win.
Best Answer
The standard strategy for solving problems like this starts with thinking that you're in the middle of playing this game with $0$ coins in the pile and your turn, and see who wins (it has to be your opponent, because on their previous turn, they removed the last coin and won).
The problem already tells you that modulo 4 is important, so next we look at what happens if there instead are $1, 2, 3$ or $4$ coins and your turn. Can the you win any of them? Can your opponent guarantee a win in any of them?
Next, for $5, 6, 7$ or $8$, can you force the opponent into a position that the previous paragraph deemed as "the current player loses"? If not, can your opponent do that to you no matter what you try?
A pattern should start to emerge. What does the winning strategy seem to be? With the intuition you've built from working through the above, it shouldn't be too hard to prove by doing the above paragraph of $5, 6, 7, 8$ in general using induction. (The induction parameter isn't really "How many coins there are on the table", but rather "How many groups of four coins there are", and then the induction step itself is split into four cases depending on how many coins are left modulo 4.)