how to combine recursive feature elimination and grid/random search inside one CV loop? I've seen taught several places that feature selection needs to be inside the CV training loop.  Here are three examples where I have seen this:
Feature selection and cross-validation
Nested cross-validation and feature selection: when to perform the feature selection?
https://machinelearningmastery.com/an-introduction-to-feature-selection/

...you must include feature selection within the inner-loop when you
  are using accuracy estimation methods such as cross-validation. This
  means that feature selection is performed on the prepared fold right
  before the model is trained. A mistake would be to perform feature
  selection first to prepare your data, then perform model selection and
  training on the selected features...

Here is an example from the sklearn docs, that shows how to do recursive feature elimination with regular n-fold cross validation.
However I'd like to do recursive feature elimination inside random/grid CV, so that "feature selection is performed on the prepared fold right before the model is trained (on the random/grid selected params for that fold)", so that data from other folds influence neither feature selection nor hyperparameter optimization.
Is this possible natively with sklearn methods and/or pipelines?  Basically, I'm trying to find an sklearn native way to do this before I go code it from scratch.
 A: If you want to search over the number of features to retain, then you need some sort of cross-validation, and since as you point out this needs to be done inside the training set of the main model fit, this will require nested cross-validation.  If that's not a computational problem for you, then sklearn makes this pretty simple.
from sklearn.model_selection import RandomizedSearchCV
from sklearn.pipeline import Pipeline

pipe = Pipeline(steps=[('feat_sel', RFECV(...)),
                       # ...other preprocessing?...
                       ('model', LogisticRegression(...)) # or whatever
                      ])
search = RandomizedSearchCV(estimator=pipe, ...)
search.fit(X, y)

Note that you could provide your own cross-validation instead of the default k-fold, if you need to save some computation time.
The other option is to use RFE instead of RFECV, which requires a fixed number of features to use, but then doesn't need its own cross-validation; this seems best if you have some domain or previous model information to suggest the right number of features in advance (be sure not to use your whole training set to determine that!).
A: Using the Randomized/Grid search CV you can also use the simple RFE without nesting another CV inside the main one. In this case, you should specify among the parameters searched during the grid/randomized search also the number of features that you want to test in order to find the optimal one. Combining this RFE with the machine-learning algorithm of your choice in a pipeline, will allow you to use the selected features during the fit phase that will be performed on the same set of data used by the RFE. I repropose here the same example in Ben's answer with the here proposed method:
from sklearn.model_selection import RandomizedSearchCV
from sklearn.pipeline import Pipeline

pipe = Pipeline(steps=[('feat_sel', RFE(estimator=..., step=1)),
                       # ...other preprocessing?...
                       ('model', LogisticRegression(...)) # or whatever
                      ]
               )
param_distributions = {
                       # specify here the number of features you want to test using the RFE method
                       'feat_sel__n_features_to_select': [4,5,6,7,8,9,10] 
                       # ... other parameters you want to search ...
                      }

search = RandomizedSearchCV(estimator=pipe,
                            param_distributions=param_distributions, ...)
search.fit(X, y)

