digitalRead sampling rate for Arduino Uno
You have two problems right now that are separate from each other.

1) Button bounce

2) Improper button wiring

First, you need to introduce a delay into your interrupt function so that it won't keep registering each rise and fall of the bounce as a separate button press. Use "delayMicroseconds()" because apparently you can't use regular "delay()" inside interrupts. Id suggest a 20,000 microsecond delay.

Second, you need to put a pull down resistor onto the digital pin that you are sampling. 

The problem you are having is that the pin is in input mode and thus at high impedance (very high resistance) and thus has a tenancy to "float". If you put a voltage to it, it charges up like a capacitor and since the pin itself has very high resistance to ground, it takes a while for the charge to dissipate to the point where the Arduino will register a LOW again. A 10k resistor from the pin to ground will force the "capacitor" to discharge quickly after current from the button has stopped flowing.

Finally, the Arduino is pretty quick at it's read/write operations (I'm a mechanical engineer, ALL electronics happen "quickly" in comparison to mechanical systems, so it's relative I guess). Here's a link to some test results. 

TL;DR verson:

What these values tell me, is that we can do about:

10 analog 10-bit readings per millisecond with analogRead()
128 pwm settings per millisecond with analogWrite()
220 pin reads per millisecond with digitalRead()
224 pin writes per millisecond with digitalWrite()
1056 pin reads per millisecond with direct port reads
1059 pin writes per millisecond with direct port writes