I have a Nokia 6500S-1 which I previously used as a 3G modem (with Windows). Is it possible for an Android device to use this phone as a modem (just like the windows PC does), but expose the modem functionality thru bluetooth instead of USB?
Yes, your phone supports two ways to export its internet connection via bluetooth:
See also this question (its answer about bluetooth).
In short: PAN is supported from Android 3.0 onwards as client. Android <3.0 users may have luck with Wireless tether for root users. DUN is not supported out of the box, there are apps though. Go for PAN if it works for you (DUN requires parameter and possibly eats more battery).