Instead of fitting whole shapes onto the board, make a "filling" algorithm that will create shapes at the end. For example, if you want to fill square with 4-block shapes, it could look like this:
1) create an array
2) look for free spot on board (either random or picked somehow)
3) add Vector2 of this position to your array
4) check all spots next to that block to see if they are free
5) choose random free neighboring spot
6) add this position to your array
7) if you have less than 4 elements in array, repeat from step 4
Now that you have the vector array, you need a table of possible shapes. Look up the table and select proper shape to place it, so that its blocks fit the vectors in array. You might want to translate the vectors first, so their top-left is at (0, 0), because your look-up table might be that way too.
Just repeat these steps until your board is filled. And if it fails because there's a hole impossible to fit with proper shape, you can either remove last X shapes and try again or start over.
Not sure if it will work perfectly, but if I were to do this, I'd first try this way.