First, I am confused whether at each node in all the trees, do we
randomly pick features from the lot to be pitted for best split or
does each tree get a random subset of feature and then all the nodes
in that tree have to work with those features?
m-features are chosen randomly at each split of the tree, not at the creation of the tree itself.
Now, regardless of the case whether we pick random features at tree or node level, why do choose random subset of data for each tree? Because if the features are different at tree/node level, the trees will be different. Why do we need to add another level and make the distribution of data also random to the trees and not just feed the complete original dataset to the trees?
This is exactly what makes random forests unique compared to other algorithms. Indeed, we sample with replacement (bootstrap) from the training dataset and each bootstrap sample is unique to each tree (which you appear to understand).
However, we need to consider how the final predictions come out of a random forest in the first place. Recall that the final prediction for an observation $y_i$ will be the average predicted probability among all of the trees in the forest. This is supposed to work because, under the (crucial) assumption of zero/negative correlation between the trees, we know that the sample mean has variance that goes to zero as n goes to infinity. This is one key element of random forests; if I have a bunch of overfit trees (low bias, high variance) I can simply get rid of this high variance for each tree by combining the predictions of each individual tree and averaging. The result is hopefully low bias, and low enough variance for my final, combined model.
However, if there is positive correlation among the trees, the variance of the sample mean actually increases (as $ n \rightarrow \infty$) and if n is large enough, the covariance between the trees actually starts to dominate the variance of each individual tree itself. What this results in is a decrease in predictive performance compared to just using a single (or relatively few) tree(s). After all, the whole point is to fit low bias, high variance base learners and to then reduce the variance by averaging. If we now cannot reduce the variance due to correlation between base learners (and start increasing it instead!), our model is likely to be severely overfit, even moreso than using a comparatively less overfit base learner.
So the question becomes...how do we reduce the correlation between the trees? One solution is to introduce randomness not only through the data sample itself (i.e. bootstrap/sample with replacement) but also through randomly selecting predictors at each split of a node. By doing this, we hopefully force each tree to learn something different about the data. Indeed, if only a few predictors are useful than chances are, all of the trees will pick up on this and stick to using these few predictors over and over again. The result is that all of the trees have learned exactly the same thing, substantial correlation among the trees, and not much purpose to using the trees together.
Bagging (which is what you refer to as the first level of randomness) and other ensembling based methods work best when we have what people call "diverse base learners". This means that in general, if we can find many models that are similar in performance but uncorrelated (that is, they have learned different, but equally important parts of the data) then combining the models in some fashion will almost certainly be better than using either one alone. Creating model diversity is difficult but some common ways are;
1) Do something similar to random forests; give each base learner a different set of features to use.
2) Use different algorithms that hopefully learn different parts of the data due to the differences in how they are fit; example: random forest + neural network + gradient boosting, etc.
