Why are alkali metal compounds like sodium hydride or sodium amide strong bases but weak nucleophiles? I understand why compounds such as $\ce{NaH}$ or $\ce{NaNH2}$ are weak nucleophiles: as they aren't very soluble in organic solvents, they react only on the clusters' surface. But why are they strong bases?

I could understand why they are in water, as they are soluble in water, but in my organic chemistry class it was said that they accelerate E2 reactions. So how can they be strong bases in organic solvents if they aren't soluble in organic solvents?
You're right they're difficult to use in organic reactions because of the solubility problem you mention. However, by using crown ethers like dibenzo-18-crown-6 they can be captured and the crown ethers are subsequently dissolved so that the bases are "brought into solution" and react.