You don't define your problem very clearly but under any interpretation there are no really easy answers. I assume that you have some squares you wish to cover, some you don't care if you cover or not ("already covered") and some you must leave uncovered ("outside the region") You seem to permit overlapping tetrominos but would prefer to use as few as possible (so no overlaps if possible) There are seven tetrominos (or five if you allow reflections). Are you saying that you can use any mix of them?
It is a pretty well worked out, but far from trivial matter to say how many ways one can fill an empty rectangle with dominoes. So any version of your question would be difficult (even using only 1x4 and 4x1 tiles). There are various simple and not so simple criteria for a perfect tiling but they are usually applied to the situation with all tiles congruent. One can translate certain NP complete problems into simple seeming exact cover tiling problems so in general there is decision algorithm.
If you say no overlaps then this is one example of packing/exact-cover as are Soduku and the n queens problem. After you write your program you should check out this amazing algorithm of Donald Knuth.