Question (2) is a known problem; it's called the change-making problem. The Wikipedia page lists integer programming and dynamic programming as solution approaches. The change-making problem is also a variation of the famous knapsack problem. One of the implications of that is that since the standard version of the knapsack problem is NP-complete, it's likely that the change-making problem is as well, dashing hopes for an easy-to-find fast algorithm for solving it.
However, the Wikipedia page also says that for the US and most other coin systems, the greedy algorithm will give the optimal solution. Thus for the nickel/dime/quarter example you give, the optimal solution is to use as many quarters as you can, then account for what's left by using as many dimes as you can, then make up the rest with nickels. So 3 is the minimum number of nickels, dimes, and quarters required to make 40 cents.
Here's the integer program formulation for Question (2). If you let $x_i$ be the number of coins of type $i$ to be used, $d_i$ be the denomination of coin type $i$, and $A$ be the target amount, Question (2) entails solving
$$\min \sum_i x_i $$
subject to
$$\sum_i d_i x_i = A,$$
$$x_i \geq 0, x_i \in \mathbb{Z}.$$
While integer programs are hard to solve in general, for small problems like the example you give a good IP solver will return a solution very quickly. For instance, if you take coins of denominations 31, 37, and 41 cents (since nickels, dimes, and quarters are too easy :) ), and want to know the minimum number required to be equivalent to 2011 cents, the solver Lingo requires only the following code to find the answer:
MIN = x1 + x2 + x3;
31*x1 + 37*x2 + 41*x3 = 2011;
@GIN(x1); @GIN(x2); @GIN(x3);
Lingo outputs the optimal solution as $x_1 = 0, x_2 = 20, x_3 = 31,$ with only 7 solver iterations and "00:00:00" time elapsed. So the minimum number of coins is $51$.
You did ask specifically for an algorithm. Many IP solvers (including Lingo) use the branch and bound algorithm, which has solving a linear program (usually with the simplex method) embedded in it.
For Question (1), you could use the following integer program to find a single solution or determine that one does not exist. (In the latter case, the IP solver will report that the problem is infeasible.)
$$\max 1$$
subject to
$$\sum_i d_i x_i = A,$$
$$\sum_i x_i = n,$$
$$x_i \geq 0, x_i \in \mathbb{Z}.$$
Again, for small problems a good IP solver will return a solution almost instantaneously. I'm not sure how (or even if it's possible) to modify an IP approach to find all solutions like you request. The generating function techniques mentioned by cardinal and in the question linked to by Derek Jennings will tell you how many solutions there are, but I'm not sure if they will tell you exactly what those solutions are.
If you change $p$ to "$n$ cents has been changed into quarters, dimes, nickels, and pennies using the fewest coins possible," and $q$ to "at most two dimes, at most one nickel, at most four pennies have been used, and two dime and a nickel have not been used," I think you'll see it.
Best Answer
Here's the generating function solution:
The generating function that counts all ways of making change is:
$$ \text{all}(x) = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})} $$
[That is, the coefficient of $x^{100}$ is the number of ways to make change of a dollar.]
If we look at the function
$$ \text{alternating}(x) = \frac{1}{(1+x)(1+x^5)(1+x^{10})(1+x^{25})} $$
Then the coefficient of $x^{100}$ is (number of ways to do it with even number of coins) - (number of ways to do it with odd number of coins) [can you see why?]. From here you can easily solve for both (even number of ways) and (odd number of ways).