Yes, it's very common to use both tricks. They solve different problems and can work well together.
One way to think about it is that weight decay changes the function that's being optimized, while momentum changes the path you take to the optimum.
Weight decay, by shrinking your coefficients toward zero, ensures that you find a local optimum with small-magnitude parameters. This is usually crucial for avoiding overfitting (although other kinds of constraints on the weights can work too). As a side benefit, it can also make the model easier to optimize, by making the objective function more convex.
Once you have an objective function, you have to decide how to move around on it. Steepest descent on the gradient is the simplest approach, but you're right that fluctuations can be a big problem. Adding momentum helps solve that problem. If you're working with batch updates (which is usually a bad idea with neural networks) Newton-type steps are another option. The new "hot" approaches are based on Nesterov's accelerated gradient and so-called "Hessian-Free" optimization.
But regardless of which of these update rules you use (momentum, Newton, etc.), you're still working with the same objective function, which is determined by your error function (e.g. squared error) and other constraints (e.g. weight decay). The main question when deciding which of these to use is how quickly you'll get to a good set of weights.
It is not surprising that weight decay will hurt performance of your neural network at some point. Let the prediction loss of your net be $\mathcal{L}$ and the weight decay loss $\mathcal{R}$. Given a coefficient $\lambda$ that establishes a tradeoff between the two, one optimises
$$
\mathcal{L} + \lambda \mathcal{R}.
$$
At the optimium of this loss, the gradients of both terms will have to sum up to zero:
$$
\triangledown \mathcal{L} = -\lambda \triangledown \mathcal{R}.
$$
This makes clear that we will not be at an optimium of the training loss. Even more so, the higher $\lambda$ the steeper the gradient of $\mathcal{L}$, which in the case of convex loss functions implies a higher distance from the optimum.
Best Answer
The learning rate is a parameter that determines how much an updating step influences the current value of the weights. While weight decay is an additional term in the weight update rule that causes the weights to exponentially decay to zero, if no other update is scheduled.
So let's say that we have a cost or error function $E(\mathbf{w})$ that we want to minimize. Gradient descent tells us to modify the weights $\mathbf{w}$ in the direction of steepest descent in $E$: \begin{equation} w_i \leftarrow w_i-\eta\frac{\partial E}{\partial w_i}, \end{equation} where $\eta$ is the learning rate, and if it's large you will have a correspondingly large modification of the weights $w_i$ (in general it shouldn't be too large, otherwise you'll overshoot the local minimum in your cost function).
In order to effectively limit the number of free parameters in your model so as to avoid over-fitting, it is possible to regularize the cost function. An easy way to do that is by introducing a zero mean Gaussian prior over the weights, which is equivalent to changing the cost function to $\widetilde{E}(\mathbf{w})=E(\mathbf{w})+\frac{\lambda}{2}\mathbf{w}^2$. In practice this penalizes large weights and effectively limits the freedom in your model. The regularization parameter $\lambda$ determines how you trade off the original cost $E$ with the large weights penalization.
Applying gradient descent to this new cost function we obtain: \begin{equation} w_i \leftarrow w_i-\eta\frac{\partial E}{\partial w_i}-\eta\lambda w_i. \end{equation} The new term $-\eta\lambda w_i$ coming from the regularization causes the weight to decay in proportion to its size.