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 -
link[
^] (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.