You can exchange bitcoins on IRC for prepaid virtual visas and mastercards, paypal, any 3rd party payment you want. There's a few web services for exchanging coins to visa too, which I can't remember right now but are posted to bitcointalk forums.

Of course if you were setting up an illegal hidden service payment would be the least of your worries. Moving it around every few weeks inside Russia like the inter-dimensional dark fortress in Krull to prevent long term traffic analysis, maintaining your site from a moving location everyday, and making sure you don't blow opsec giving away your identity is probably more difficult than finding creative methods to pay for hosting.