Yes. This would in fact be possible. This is not a case of the halting problem as the case is defined, not arbitrary. To answer this, two parts must be answered; first if a solution exists can it be found, and second will there always be a valid solution to find.
The first part of is how to find a set of replacement tiles (gems) which would produce a playable board. This can be achieved via brute force methods, just check every possible replacement set until a playable one is encountered (There would be more optimal non-brute force methods as well).
The second part is to determine if there will always be a replacement set which will produce a playable set. Any set of tiles removed in a single move is going to be some superset of sets of three tiles, so if in the minimal case of only three being removed, if a playable set can always be found, then for all possible patterns of removed tiles there will be a playable set, as it will contain all the solutions for each set of three removed tiles which is a subset of the removed tiles.
In the minimal case of clearing only three tiles in a row/column, A replacement set containing two tiles of type A separated by a tile of type B (where type A is the type of a tile above or below the cleared set of three in the case of a column of three, or to the left or right in the case of a row of three). This will yield a move where swapping the center of these three tiles with the appropriate A tile alongside it will produce a set of three. This shows that a set of tiles can always be found which will produce a valid move along the column/row where the original tiles were cleared. Restricting future moves to that column or row would, while being a valid solution for an infinity playable game, would not be very fun. But using all the rules for common bejeweled style games, it’s easy to show that there will always exists a solution which will allow for moves outside of that row/column as well. Assume we drop in three A type tiles, where A is one of the tiles above or below / left or right of the removed set of three. This will produce a “bomb” style tile which will clear an area when removed. If we then drop in another replacement set of tiles which results in a match being made with that bomb an area of tiles will be cleared. This area will contain a number of 3 tile subsets within other rows, which means that that future moves will not necessarily be limited to a single row/column.