Is the momentum of a particle both uncertain and, independently, also random? Is momentum of a particle "random" because it is uncertain, or is it uncertain in addition to being random?
Is the uncertainty principle and quantum randomness different names the same physical phenomenon, or separate phenomena? Does anybody know?
 A: A particle is a wave. It's wave function (consider non relativistic Quantum Mechanics), when absolute valued squared, is a probability density function. The particle's momentum is a multiple of the gradient of the wave function, with h, Planck's constant, one of the proportionality constants. That is then the probability density function for momentum. It is uncertain because it is a random value, and you can use that probability density function to calculate its average and it's standard deviation. 
It's standard deviation time that of the particle's position (calculated from the wave function's pdf with position as the variable to calculate the standard deviation of), has to be greater than or equal to h over 2 pi. That's the uncertainty principle.
In essence they are random and the wave function with some rules (derived from quantum mechanics) on what applies to position and what to momentum is used to calculate probable values as well as uncertainties. It is not that mysterious. How people came up with those rules, i.e. Quantum mechanics and how to calculate the different physical entities, and why they make sense, is a longer story. A first basic course or book on quantum mechanics will explain it. 
Hope this helps.  
A: 
Is momentum of a particle "random" because it is uncertain, or is it uncertain in addition to being random?

In quantum mechanics systems are represented using wave-functions (wave-vectors). The momentum of a particle is completely uncertain if it's position is certain (a localized particle) . But it is also possible to create wave-functions that have a fixed or certain momentum but these will give completely random positions if you try to measure where the particle is. So the uncertainty is a trade-off, this is what the uncertainty  principle says.
The randomness is a consequence of this uncertainty. Suppose you had multiple copies of a state that has an uncertain value of momentum. If you were to measure the momentum of these states you would get random numbers whose statistical variance is proportional to the uncertainty in momentum as predicted by the uncertainty principle.    

Is the uncertainty principle and quantum randomness different names the same physical phenomenon, or separate phenomena? 

Both are related. But I wouldn't call them the same. Both of them arise from the probabilistic nature of QM .The uncertainty principle connects the variance in observed values between two observables which don't commute. But the randomness in measurement itself arises from the superposition principle and how the state behaves when it is measured.  It is better to understand these phenomena from the fundamental axioms of QM rather than worrying about semantics.
