As a summary, here are the different possibilities available to you.

#The Easy Way

As often in Mathematica, the easiest way is usually to use a built-in construct. As @Lukas mentioned in the comments, you can use the special height specification "Probability" in Histogram[] to get what you want.

data=Table[RandomInteger[],{1000}]
Histogram[data,Automatic,"Probability"]

#The Alternative

But maybe, as @Jim Baldwin said, an alternative visualisation is best? Sometimes, you can't beat a simple table...

counts = Tally@Table[RandomInteger[], {1000}];
Grid[{Text /@ {"", "heads", "tails"}, 
  Text /@ {"count", counts[[1, 2]], counts[[2, 2]]}, 
  Text /@ {"probability", N[counts[[1, 2]]/1000], 
    N[counts[[2, 2]]/1000]}}, Frame -> All]

#The Straight Answer Strictly speaking however, you are asking to normalize the histogram scale. To do this, you need to define a custom height function as defined in the "Details and Options" section of the reference on Histogram.

heightfunction[bins_, counts_] := counts/1000;
Histogram[Table[RandomInteger[], {1000}], {{0, 0.5, 1.1}}, heightfunction]

Note: I also adjusted the bins to remove the empty space on the left

As a summary, here are the different possibilities available to you.

The Easy Way

As often in Mathematica, the easiest way is usually to use a built-in construct. As @Lukas mentioned in the comments, you can use the special height specification "Probability" in Histogram[] to get what you want.

data=Table[RandomInteger[],{1000}]
Histogram[data,Automatic,"Probability"]

The Alternative

But maybe, as @Jim Baldwin said, an alternative visualisation is best? Sometimes, you can't beat a simple table...

counts = Tally@Table[RandomInteger[], {1000}];
Grid[{Text /@ {"", "heads", "tails"}, 
  Text /@ {"count", counts[[1, 2]], counts[[2, 2]]}, 
  Text /@ {"probability", N[counts[[1, 2]]/1000], 
    N[counts[[2, 2]]/1000]}}, Frame -> All]

The Straight Answer

Strictly speaking however, you are asking to normalize the histogram scale. To do this, you need to define a custom height function as defined in the "Details and Options" section of the reference on Histogram.

heightfunction[bins_, counts_] := counts/1000;
Histogram[Table[RandomInteger[], {1000}], {{0, 0.5, 1.1}}, heightfunction]

Note: I also adjusted the bins to remove the empty space on the left