Is it possible to update iPhone4  to a provider-neutral OS so WiFi hotspot can be enabled? I want to use an original (non jailbroken) iPhone4 to access the internet with an iPad. 

This should is possible using the Personal wifi hotspot included in iOS 4.3 as mentioned in Can I use tethering to share my iPhone&#39;s connection with my iPad?, however some providers (such as the Dutch T-mobile) have removed this feature in a localised version of the OS.

Is there a (legitimate) way to update to a "generic" iOS so I can use the Personal Hotspot to tether my iPad or is there another (legitimate) way to not have to get the 3G iPad and an extra sim card.

Please note I am in Europe, i.e. not on AT&amp;T or Verizon
It is not a carrier localized version of the OS that is installed on the iPhone. There is one iOS release image for each hardware model. What changes for each mobile network is the carrier settings, which is downloaded either OTA (iOS4+) or by iTunes when the phone is activated or connected and an update is available.  

If you have the released from any carrier lock then if you move to another mobile provider supporting the tethering feature then their carrier settings will enable the preference.