I believe the best (only?) way to accomplish this will be through Markov Chain Monte Carlo sampling:
http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo
This will allow you to sample from the unknown posterior without knowing it's functional form.
These are really more like questions than a better answer, but this seemed the best place to put them:
First, you can reformulate the problem in terms of only $k-1$ unknowns since the last one is functionally dependent (the $p$'s must sum to one).
Assuming $f_i$ represents the observed frequency of each case (please correct that assumption if it's wrong), why include it as part of the prior? I'd suggest that your prior should not depend on the data. You might use an exponent of 0 to represent a vague prior instead.
Unless $k$ is huge, this problem is easily solved by MCMC. You could set it up in Winbugs or PyMC if you don't want to write your own code. Also, with MCMC, the above derivations aren't needed. You only need to specify the prior (which may just be constant) and the likelihood (which is pretty simple).
I'd also suggest not trying to simulate the posterior predictive directly, but instead simulate the posterior first and then the predictive is easily obtained from that by simulation.