This is a Bernoulli process, a stochastic process which has two outcomes, success ("the marble is in $A$!") and failure ("the marble is not in $A$."). Let $s$ denote the probability of success and $f$ denote the probability of failure.
The formula for the probability of $k$ successes in $n$ trials is
$$Pr[k\mbox{ successes in }n\mbox{ trials }] = \binom{n}{k}s^kf^{n-k}.$$
Where did this come from? There are $\binom{n}{k}$ different ways of arranging those $k$ successes among the $n$ tries. By independence, each of those different ways has probability $s^kf^{n-k}$ --- there are $k$ successes and the rest, all $n-k$ of them, are failures. Since we're not interested in the order of the successes, just the total number, we can add up the probabilities of all the different ways of getting $k$ successes in $n$ trials to arrive at the formula.
In your case, $s = \frac{1}{4}$, $f = \frac{3}{4}$, and $n=4$. Now we see that your first idea is correct: $$Pr[0\mbox{ successes }] = \binom{4}{0}\bigg(\frac{1}{4}\bigg)^0\bigg(\frac{3}{4}\bigg)^4 = \bigg(\frac{3}{4}\bigg)^4.$$
What about your second idea? Let's think this through. For the denominator, we want to count the number of ways of distributing $4$ marbles among $4$ buckets. Let's think of this as a process: first we'll toss the first marble, then we'll toss the second marble, and so forth. How many options does the first marble have? $4$. The second? Again, $4$. So on. By the independence of the marble dropping, there are $4^4$ possible outcomes for this experiment. Repeating the argument, there are $3^4$ outcomes in which the $A$ bucket does not receive any marbles. Hence, $\frac{3^4}{4^4} = \big(\frac{3}{4}\big)^4$, just as we computed above.
Edit: After reading Andre Nicolas' answer, I want to add the following. One can only use counting to compute probability if all outcomes are equally likely. But as he notes, not all the multisets are equally likely! Some may be arrived at via multiple routes through the experiment's tree; for example, $\{A,A,A,A\}$ can only happen one way, while $\{A,B,C,D\}$ can happen $4!$ ways, since, e.g., $\{A,B,C,D\}=\{D,C,B,A\}$. So if you want to think in terms ofmultisets, you need to modify your counting. Take the different types of multisets (all one bucket, two buckets, three buckets, all four buckets), count the number of multisets in each type and multiply by the number of ways each multiset can occur, then add everything together.
Let
$$m^2=n^2+204n$$
$$k^2=n^2+204n+10404=(n+102)^2$$
Then
$$(k-m)(k+m)=2^2\cdot 3^2\cdot 17^2$$
Since $k-m$ and $k+m$ have the same parity, they must be even. Write:
$$\frac{k-m}2\frac{k+m}2=3^2\cdot17^2$$
Since $k>m$ there are only two options: $k-m=2$ and $k-m=18$. The former gives $m=2600$ and the latter $m=280$. Thus we are interested in the former, which gives $n=2500$.
Best Answer
Observations towards a solution.
Prove the following. If you're stuck, state what you've tried.
I agree with you that no closed-form expression is known, so that likely isn't what they were expecting.
Maybe check the original writeup (see if they were asked to prove it's the number of partitions). It might also be possible that they got the problem wrong.