The answer depends a lot on the exact components you use, and what the parameters are of your circuit.
First, lets consider battery voltage. You can't get a rechargeable battery in an arbitrary voltage. NiCd are 1.2V nominal, and Lithium-Ion are 3.7V nominal. Neither of these gives you exactly 5V, and the voltage will vary significantly over the charge/discharge cycle. So, first question is, does your circuit need EXACTLY 5V, or is 4-6ish V OK? If you need exactly 5V, the 5V battery solution probably isn't for you.
Next, let's think about the 12V to 5V converter. It'll probably be between 90% and 95% efficient, so that's one point in favor of the 5V battery solution (which might not need a DC-DC converter).
And, finally, what do your solar cells look like? How much control do you have over the number of cells in series? A single solar cell is maybe 0.5V, but most solar panels will have several cells in series. Is your solar panel closer to 12V output, or 5V output? If your 5V solar charger incorporates a 12V to 5V converter, it will have 90-95% efficiency just like the one above, and negate that point in favor of the 5V battery. If your solar charger uses direct energy transfer (no DC-DC converter) it will have higher efficiency - but may have other disadvantages (too complex to get in to here).
In the end, the optimal solution depends on a lot of variables, and you will need to take each into account to calculate the overall system power efficiency.