When all boiled down, it seems that your question relates to the Packing Problem class of problems (http://en.wikipedia.org/wiki/Packing_problem
A question on SO that seems almost identical to yours may be found here: http://stackoverflow.com/questions/3516044/fill-arbitrary-2d-shape-with-given-set-of-rectangles
The accepted answer to that question makes reference to a research paper from 1982 by András Hegedüs, called Algorithms for covering polygons by rectangles
] (which costs $35 or requires appropriate institute access) and makes the suggestion to search for papers that cite it.
There are almost certainly open-source implementations of the algorithm it describes. With some time and the right search-terms, you'll hopefully be able to find something useful.