How do you measure how "predictable" a dataset is? Is there a way to measure how "predictable" a dataset is based on some of its inherent attributes such as its entropy level or its amount of self-similarity? 
If so, how is that "predictability score" related to your confidence level of any possible prediction in the future?
Allow me to ask this question with an example:
Consider you have the first 50 data points for a straight line: y = x (but you don't know for sure that y = x is the formula that produced the data points). You're asked to predict the next n number of data points where n is as far into the future as you feel comfortable. 
Certainly, you would feel very confident predicting the next few data points, or the next 50 or more as continuing along in the same vein: y = x. But at some point you would say, "Well, what are the chances that my prediction, at y = 10^100 is x = 10^100?" maybe the chances are less than y = 51 so x = 51. 
So even with a straight line as the dataset, you may not know if that straight line was a blip in an otherwise curvey structure or if it should be straight forever. So you have to discount your confidence when making predictions about it into the future when extrapolating what you think you might know.
When you have more chaotic data, of course, the rate at which your confidence at being able to predict it's future goes down faster.
The question is: How do you calculate how quickly your confidence diminishes to chance given a dataset, that is, before ever actually making a prediction? How do I get the prior likelihood that I can't be better than chance Z predicted datapoints out into the future?

 A: In a regression setting, this comes down to the level of observation noise and how much entropy is in the posterior distribution of the parameters of your chosen model. 
In particular, the uncertainty of the model parameters will automatically result in larger variance in predictions the further away you move from the available data. 
If you are not familiar with Gaussian Processes, I think you would get a lot out of studying those, in regard to this question. You can download for free one of the best texts here:
http://www.gaussianprocess.org/gpml/
or check out these nice videos:
http://videolectures.net/mlss09uk_rasmussen_gp/
A: You need to make more assumptions to address this question. No matter the model you will propose, there will always be a (model depending) data set for which your model will be always wrong. 
Mathematical construction
This is actually quite easy to build, say for a dataset $A=(x_i,y_i)_{i \in I}$ where the $y_i$ are some $(0-1)$ labels and $x_i$ some inputs. Now you may train $\hat{f}$ on $A$ any way you want, if you try to generalize your model on unseen $x_i$'s, I can build $B=(x_i,1-\hat{f}(x_{i}))_{i\in J}$. It makes sure that your model will perform very badly.
The intuition
Starting from your claim :

If so, how is that "predictability score" related to your confidence level of any possible prediction in the future?

Without any assumption on the model or on the data, imagine the following scenario. You chose a model based on the best "predictability score" you defined, and claim this model to be the best. Then, I propose you a data-set which says the exact opposite of what your model could predict (or purely random labels). On this data set, your model would perform as poorly as I want, though it would have a the best "predictability score", questioning the relevance of this score.
How to overcome this ?
Obviously this example is pathological. I could not propose such a construction if you had said, in the first place that the data is linearly separable. In this case, I could not have built a data set as I just did.
The practical point of view
Usually, when doing any model on the data, you assume that the distribution and patterns you observe will remain identical. When you want to estimate the performance on unseen data, statisticians often rely on cross validation to estimate the future performance of their models. To some extent, you may view it as an "empirical predictability score".
