There's no unique solution
I don't think that true discrete probability distribution can be recovered, unless you make some additional assumptions. Your situation is basically a problem of recovering the joint distribution from marginals. It is sometimes solved by using copulas in the industry, for example financial risk management, but usually for continuous distributions.
Presence, Independent, AS 205
In the presence problem no more than one bomb is allowed in a cell. Again, for the special case of independence, there is relatively efficient computational solution.
If you know FORTRAN, you can use this code that implements AS 205 Algorithm: Ian Saunders, Algorithm AS 205: Enumeration of R x C Tables with Repeated Row Totals, Applied Statistics, Volume 33, Number 3, 1984, pages 340-352. It's related to Panefield's algo that @Glen_B referred to.
This algo enumerates all presence tables, i.e. goes through all possible tables where only one bomb is in a field. It also calculates the multiplicity, i.e. multiple tables that look the same, and calculates some probabilities (not those you're interested in). With this algorithm you may be able to run the complete enumeration faster than you did before.
Presence, not independent
The AS 205 algorithm can be applied to a case where the rows and columns are not independent. In this case you'd have to apply different weights to each table generated by the enumeration logic. The weight will depend on the process of placement of bombs.
The count problem allows more than one bomb placed in a cell, of course. The special case of independent rows and columns of count problem is easy: $P_i^j=P_i\times P^j$
where $P_i$ and $P^j$ are marginals of rows and columns. For instance, row $P_6=3/15=0.2$ and column $P^3=3/15=0.2$, hence the probability that a bomb is in row 6 and column 3 is $P_6^3=0.04$. You actually produced this distribution in your first table.
Counts, Not independent, Discrete Copulas
In order to solve the counts problem where rows and columns are not independent, we could apply discrete copulas. They have issues: they're not unique. It doesn't make them useless though. So, I'd try applying discrete copulas. You can find a good overview of them in Genest, C. and J. Nešlehová (2007). A primer on copulas for count data. Astin Bull. 37(2), 475–515.
Copulas can be especially useful, as they usually allow to explicitly induce dependence, or to estimate it from data when the data is available. I mean the dependence of row and columns when placing bombs. For instance, it could be the case when if the bomb is one the first row, then it is more likely that it will be one the first column too.
Let's apply Kimeldorf and Sampson copula to your data, assuming again that more than one bomb can be placed in a cell. The copula for a dependency parameter $\theta$ is defined as:
You can think of $\theta$ as an analog of the correlation coefficient.
Let's start with the case of weak dependence, $\theta=0.000001$, where we have the following probabilities (PMF) and marginal PDFs are shown too on the panels on the right and at the bottom:
You can see how in the column 5 the second row probability does have twice higher probability than the first row. This is not wrong contrary to what you seemed to imply in your question. All probability do add up to 100%, of course, as do the marginals on the panels match the frequencies. For instance, the column 5 in the lower panel shows 1/3 which corresponds to stated 5 bombs out of total 15 as expected.
For stronger dependency (positive correlation) with $\theta=10$ we have the following:
The same for stronger but negative correlation (dependency) $\theta=-0.2$:
You can see that all probabilities add up to 100%, of course. Also, you can see how dependency impacts the PMF's shape. For positive dependency (correlation) you get the highest PMF concentrated on the diagonal, while for the negative dependency it is off-diagonal