If there is one algorithm that I wouldn't use in this case, it is knn.
You might try the kknn package "(via caret or directly) but the storage problem will remain.
There's also LVQ, which you can get through caret but for classification 
. There's no apparent reason (that I could see) that it wouldn't be good for regression but you'd need to re-implement it based on class::lvq1.
Also, I think that you can just set aside some percentage of data to use as a single holdout for tuning.