Variable selection for predictive modeling really needed in 2016? This question has been asked on CV some yrs ago, it seems worth a repost in light of 1) order of magnitude better computing technology (e.g. parallel computing, HPC etc) and 2) newer techniques, e.g. [3].
First, some context. Let's assume the goal is not hypothesis testing, not effect estimation, but prediction on un-seen test set. So, no weight is given to any interpretable benefit. Second, let's say you cannot rule out the relevance of any predictor on subject matter consideration, ie. they all seem plausible individually or in combination with other predictors. Third, you're confront with (hundreds of) millions of predictors. Fourth, let's say you have access to AWS with an unlimited budget, so computing power is not a constraint.  
The usual reaons for variable selection are 1) efficiency; faster to fit a smaller model and cheaper to collect fewer predictors, 2) interpretation; knowing the "important" variables gives insight into the underlying process [1].
It's now widely known that many variable selection methods are ineffective and often outright dangerous (e.g. forward stepwise regression) [2].
Secondly, if the selected model is any good, one shouldn't need to cut down on the list of predictors at all. The model should do it for you. A good example is lasso, which assigns a zero coefficient to all the irrelevant variables. 
I'm aware that some people advocate using an "elephant" model, ie. toss every conceivable predictors into the fit and run with it [2].
Is there any fundamental reason to do variable selection if the goal is predictive accuracy?
[1] Reunanen, J. (2003). Overfitting in making comparisons between variable selection methods. The Journal of Machine Learning Research, 3, 1371-1382.
[2] Harrell, F. (2015). Regression modeling strategies: with applications to linear models, logistic and ordinal regression, and survival analysis. Springer.
[3] Taylor, J., & Tibshirani, R. J. (2015). Statistical learning and selective inference. Proceedings of the National Academy of Sciences, 112(25), 7629-7634.
[4] Zhou, J., Foster, D., Stine, R., & Ungar, L. (2005, August). Streaming feature selection using alpha-investing. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (pp. 384-393). ACM.
 A: As part of an algorithm for learning a purely predictive model, variable selection is not necessarily bad from a performance viewpoint nor is it automatically dangerous. However, there are some issues that one should be aware of. 
To make the question a little more concrete, let's consider the linear regression problem with
$$E(Y_i \mid X_i) = X_i^T \beta$$
for $i = 1, \ldots, N$, and $X_i$ and $\beta$ being $p$-dimensional vectors of variables and parameters, respectively. The objective is to find a good approximation of the function 
$$x \mapsto E(Y \mid X = x) = X^T \beta,$$ 
which is the prediction of $Y$ given $X = x$. This can be achieved by estimating $\beta$ using combinations of variable selection and minimisation of a loss function with or without penalisation. Model averaging or Bayesian methods may also be used, but let's focus on single model predictions.   
Stepwise selection algorithms like forward and backward variable selection can be seen as approximate attempts to solve a best subset selection problem, which is computationally hard (so hard that the improvements of computational power matters little). The interest is in finding for each $k = 1, \ldots, \min(N, p)$ the best (or at least a good) model with $k$ variables. Subsequently, we may optimise over $k$.
The danger with such a variable selection procedure is that many standard distributional results are invalid conditionally on the variable selection. This holds for standard tests and confidence intervals, and is one of the problems that Harrell [2] is warning about. Breiman also warned about model selection based on e.g. Mallows' $C_p$ in The Little Bootstrap .... Mallows' $C_p$, or AIC for that matter, do not account for the model selection, and they will give overly optimistic prediction errors. 
However, cross-validation can be used for estimating the prediction error and for selecting $k$, and variable selection can achieve a good balance between bias and variance. This is particularly true if $\beta$ has a few large coordinates with the rest close to zero $-$ as @probabilityislogic mentions.
Shrinkage methods such as ridge regression and lasso can achieve a good tradeoff between bias and variance without explicit variable selection. However, as the OP mentions, lasso does implicit variable selection. It's not really the model but rather the method for fitting the model that does variable selection. From that perspective, variable selection (implicit or explicit) is simply part of the method for fitting the model to data, and it should be regarded as such. 
Algorithms for computing the lasso estimator can benefit from variable selection (or screening). In Statistical Learning with Sparsity: The Lasso and Generalizations, Section 5.10, it it described how screening, as implemented in glmnet, is useful. It can lead to substantially faster computation of the lasso estimator.   
One personal experience is from an example where variable selection made it possible to fit a more complicated model (a generalised additive model) using the selected variables. Cross-validation results indicated that this model was superior to a number of alternatives $-$ though not to a random forest. If gamsel had been around $-$ which integrates generalised additive models with variable selection $-$ I might have considered trying it out as well. 
Edit: Since I wrote this answer there is a paper out on the particular application I had in mind. R-code for reproducing the results in the paper is available. 
In summary I will say that variable selection (in one form or the other) is and will remain to be useful $-$ even for purely predictive purposes $-$ as a way to control the bias-variance tradeoff. If not for other reasons, then at least because more complicated models may not be able to handle very large numbers of variables out-of-the-box. However, as time goes we will naturally see developments like gamsel that integrate variable selection into the estimation methodology.   
It is, of course, always essential that we regard variable selection as part of the estimation method. The danger is to believe that variable selection performs like an oracle and identifies the correct set of variables. If we believe that and proceed as if variables were not selected based on the data, then we are at risk of making errors.
A: Allow me to comment on the statement: “... fitting k parameters to n < k observations is just not going to happen.”
In chemometrics we are often interested in predictive models, and the situation k >> n is frequently encountered (e.g. in spectroscopic data). This problem is typically solved simply by projecting the observations to a lower dimensional subspace a, where a < n, before the regression (e.g. Principal Component Regression). Using Partial Least Squares Regression the projection and regression are performed simultaneously favoring quality of prediction. The methods mentioned find optimal pseudo-inverses to a (singular) covariance or correlation matrix, e.g. by singular value decomposition.
Experience shows that predictive performance of multivariate models increases when noisy variables are removed. So even if we - in a meaningful way - are able to estimate k parameters having only n equations (n < k), we strive for parsimonious models. For that purpose, variable selection becomes relevant, and much chemometric literature are devoted to this subject.
While prediction is an important objective, the projection methods at the same time offers valuable insight into e.g. patterns in data and relevance of variables. This is facilitated mainly by diverse model-plots, e.g. scores, loadings, residuals, etc...
Chemometric technology is used extensively e.g. in the industry where reliable and accurate predictions really count.
A: In several well known cases, yes, variable selection is not necessary. Deep learning has become a bit overhyped for precisely this reason. 
For example, when a convoluted neural network (http://cs231n.github.io/convolutional-networks/) tries to predict if a centered image contains a human face, the corners of the image tend to have minimal predictive value. Traditional modeling and variable selection would have the modeler remove the corner pixels as predictors; however, the convoluted neural network is smart enough to essentially discard these predictors automatically. This is true for most deep learning models that try to predict the presence of some object in an image (e.g., self drivings cars "predicting" lane markings, obstacles or other cars in frames of onboard streaming video).
Deep learning is probably overkill for a lot of traditional problems such as where datasets are small or where domain knowledge is abundant, so traditional variable selection will probably remain relevant for a long time, at least in some areas. Nonetheless, deep learning is great when you want to throw together a "pretty good" solution with minimal human intervention. It might take me many hours to handcraft and select predictors to recognize handwritten digits in images, but with a convoluted neural network and zero variable selection, I can have a state-of-the-art model in just under 20 minutes using Google's TensorFlow (https://www.tensorflow.org/versions/r0.8/tutorials/mnist/pros/index.html). 
A: In terms of prediction, you probably need to think of the question of how quickly the model learns the important features.  Even thinking of OLS, this will give you something like model selection given enough data.  But we know that it doesn't converge to this solution quickly enough - so we search for something better.
Most methods are making an assumption about the kind of betas/coefficients that are going to be encountered (like a prior distribution in a bayesian model).  They work best when these assumptions hold.  For example, ridge/lasso regression assumes most betas are on the same scale with most near zero.  They won't work as well for the "needles in a haystack" regressions where most betas are zero, and some betas are very large (i.e. scales are very different).  Feature selection may work better here - lasso can get stuck in between shrinking noise and leaving signal untouched.  Feature selection is more fickle - an effect is either "signal" or "noise".
In terms of deciding - you need to have some idea of what sort of predictor variables you have.  Do you have a few really good ones?  Or all variables are weak?  This will drive the profile of betas you will have.  And which penalty/selection methods you use (horses for courses and all that).
Feature selection is also not bad but some of the older approximations due to computational restrictions are no longer good (stepwise, forward).  Model averaging using feature selection (all 1 var models, 2 var models, etc weighted by their performance) will do a pretty good job at prediction.  But these are essentially penalising the betas through the weight given to models with that variable excluded - just not directly - and not in a convex optimisation problem sort of way.
A: I give you the perspective of industry. 
Industries don't like to spend money on sensors and monitoring systems which they don't know how much they will benefit from. 
For instance, I don't want to name, so imagine a component with 10 sensors gathering data every minute. The asset owner turns to me and asks me how well can you predict the behavior of my component with these data from 10 sensors? Then they perform a cost-benefit analysis.
Then, they have the same component with 20 sensors, they ask me, again, how well can you predict the behavior of my component with these data from 20 sensors? They perform another cost-benefit analysis. 
At each of these cases, they compare the benefit with the investment cost due to sensors installations. (This is not just adding a $10 sensor to a component. A lot of factors play a role). Here is where a variable selection analysis can be useful. 
