I still thought it was fun, but it does do pretty well at deliberately choosing "bad" pieces. With enough strategy and playing through just a couple times you can exploit weaknesses against it, however. While being very good, I was still able to score 5 lines even though it was trying to to force me out of it. As to the proof, I do believe your guess that a player can always score a line given sufficient depth. My initial thought at approaching it is to consider that the pieces must all have only 4 blocks in their structure. This is a tight limiting factor which basically gives you that you need half the width in number of pieces to get across for the most part. What makes it tricky is the shortcoming* of the algorithm you used to define the worst piece available at each turn. It, with reasonable consistency, gives you a great number of the same piece until you cross a certain boundary, so with the Z shaped pieces, for example, you can construct a row, then when you get to the last one to finish a line, it switches to straight pieces, which you can similarly line up all the way across. Repeating this process leaves you with a "hole" that is two block-widths across from very nearly top to bottom, essentially guaranteeing that you can score at least one line in the process. I'm not sure how I would formalize it exactly, but that was the strategy I employed to get 4-5 lines per game.
*shortcoming may not be the best description of the algorithm, but a better choice escapes me at the moment.