I can think of a small variation of third solution. It would be the same but some kind of foldable and/or moldable (in a real world) items, like clothes, could change its shape addapting it to an adjacent square or by compressing it, so it wouldn't be either rectangles nor squares.
This solution would possibly increase the probability to completely and automaticaly fill the inventory without human intervention. Nevertheless, items image would be shown deformed in the inventory. As a solution its image could also be shown in its description and/or more image could be created for every deformation case.
Personally I don't specially like this solution because of the image deformation but its there and might be the most voted.