The first logical consideration is that the first player can possibly either (1) buy nothing or (2) buy a silver just to pass any "first player penalty" onto the next player. Any solution kingdom needs to prevent this by making every available supply card a game losing purchase but still not as bad as buying nothing at all. While this might seem like a minor point, it may restrict the solution kingdoms to such a degree that any second player advantage has negligable effect.
I don't think it's a minor point, it greatly limits the search space...
Assume for simplicity that we would reshuffle after each turn and the winning condition would be symmetric (i.e. not differntiate if you where first or second player), which are I think the only things that prefend this from being a proof.
Then buying nothing at all would just swap the positions. By buying nothing the second player is in exactly the same position as you where before. By assumption every move he can make is a winning move for you (including, by assumption, doing nothing), which contradicts the assumption.
So under the simplifications such a board can not exist, that means that, if such a board exists the second player advantage must either involve the shuffling or is limited by the "second player compensation".