I found another potential solution, after searching off and on for a few months. I haven't tested it very much yet, so please be careful!
Saul's Solution 2, above, is the key (great suggestion!)
Basically, you combine the functionality of healpy.mollview (gnomview, cartview, and orthview work as well) with that of the reproject_to_healpix function in the reproject package (http://reproject.readthedocs.org/en/stable/).
The resulting map is suitable for my angular scales, but I can't say how accurate the transformation is compared to other methods.
-----Basic Outline----------
Step 1: Read-in the map and make the rectangular array via cartview. As Saul indicated above, this is also one way to do the rotation. If you're just doing a standard rotation/coordinate transformation, then all you need is the coord keyword. From Celestial to Galactic coordinates, set coord = ['C','G']
map_Gal = hp.cartview(map_Cel, coord=['C','G'], return_projected_map=True, xsize=desired_xsize, norm='hist',nest=False)
Step 2: Write a template all-sky FITS header (as in the example below). I wrote mine to have the same average pixel-scale as my desired HEALPix map.
Step 3: Use reproject.transform_to_healpix
reproject includes a function for mapping a "normal" array (or FITS file) into the HEALPix projection. Combine that with the ability to return the array created by healpy.mollview/cartview/orthview/gnomview, and you can rotate a HEALPix map of one coordinate system (Celestial) into another coordinate system (Galactic).
map_Gal_HP, footprint_Gal_HP = rp.reproject_to_healpix((map_Gal, target_header), coord_system_out= 'GALACTIC', nside=nside, nested=False)
It comes down, essentially, to those two commands. However you'll have to make a template header, giving the pixel scale and size corresponding to the intermediary all-sky map you want to make.
-----Full Working Example (iPython notebook format + FITS sample data)------
https://github.com/aaroncnb/healpix_coordtrans_example/tree/master
The code there should run very quickly, but that's because the maps are heavily degraded. I did the same for my NSIDE 1024 and 2048 maps, and it took
about an hour.
------Before and After Images------

