In Stephen Baxter's novel "Anti-Ice", the resident scientist builds a steam-powered rocketship using the titular phlebotinum substance, which decays with increasing intensity as the ambient temperature rises. It is used to create steam in a quantity that acts as a propellant for the rocketship.
Although IMHO the book's premise of a "Victorian Nuclear Age" isn't as well executed as, say, the "Victorian Computer Age" in "The Difference Engine", that part was a very nice touch, so I wouldn't say rockets are "un-VSF-ish" (also, Congreves).
Personally, I'd say a rocketship, possibly assisted by some antigravitic apparatus, would be reasonably victorian, and not as "outlandish" (in a good way, mind you) as a cavorite sphere or a liftwood hull.