This answer is undoubtedly a bit late for you, but maybe this'll be of some use to you or someone else in the future ...
The reason you're only being offered 3 file formats to save to in Photoshop is because the document is classified as a 'Large Document' as soon as one of the dimensions exceeds 30,000 pixels. You may already be aware of this, particularly if you created the file from scratch (at which point you'd usually see the message "Documents greater than 30,000 pixels in either dimension may not be compatible with older versions of Photoshop and/or other applications
").
Now, the Large Document (.PSB) and TIFF (.TIF / *.TIFF) file formats are technically compatible with Illustrator CS6, but you are still likely to run into problems if either dimension is much over 30,000 pixels in length. You can prove that the file format is capable of working (if you wish) by creating a comparatively 'lightweight' document that measures, say, 32,500px by 20px - Illustrator CS6 will probably tolerate that.
In layman's terms, Illustrator isn't nearly as capable as Photoshop at handling pixel-based / rasterized artwork. If you want to mix pixel-based content with your vector art, you either need to lessen the pressure on Illustrator or migrate your project to Photoshop for the latter stages of your output.
With that in mind, there are two or three solutions I can think of that would quite possibly work for the exact problem you're describing;
1.
Quite simply, chop up your pixel-based image before importing into Illustrator. Depending on the size of the imagery, Illustrator may be a little less stable if you place too much content (so save a copy as a precaution) - but three placed images that measure 12,000px by 6,000px each are going to behave much more nicely than a single image that measures 36,000px by 6,000px.
This is likely the easiest solution, if you can get away with it.
2.
Alternatively, if your work in Illustrator is otherwise finished, you can export the content to a PSD file and add your remaining large pixel-based imagery from within Photoshop directly.
Converting your Illustrator project to pixels using this method is one of the most dependable ways of ensuring that effects convert accurately within Photoshop - but this isn't a suitable solution for all situations. If you know the specification of the device you are printing to, you should be able to use export settings that match the printer's capabilities ensuring as little loss in print quality as possible. Where this method falls short is in the fact that many printers will be able to print vector-based art more accurately than pixels - and here, we've just rasterized everything, so that advantage is lost.
In truth, though, for a billboard some slightly pixellated edges may be completely imperceptible - so this might be absolutely fine. I might be a little more concerned if this were for a business card - but in that case, you wouldn't be running into this problem in the first place (unless you carry a 6-foot business card ...)
Either way, you would do well to retain your original Illustrator file so that further changes can be made to your vectors in future or on the offchance that you'll be required to print to a different specification.
3.
The third option is really a variation of number 2.
, but might be more suitable - if undoubtedly more complex.
You can also transfer your Illustrator content to Photoshop in a number of other ways - as a shape layer(s) or as a smart object(s), for example. If you import your entire Illustrator file as a smart object, you will still be able to scale your content losslessly within Photoshop, but it will output as pixels - so this isn't ultimately any better than what you would see from the second example for the purposes of print (though you WILL be able to edit the now-embedded content via Illustrator).
If, instead, you copy your vector content from Illustrator and paste it directly into Photoshop, you will have the option of defining it as a shape layer - which will STAY as a vector (assuming you save to an appropriate file format, such as PSD or export to an appropriate PDF). Pasted shape layers are just that, though - shapes. Any detailed effects work will be lost in the transfer, so you may need to re-implement some of your design using Photoshop's tools if you choose to work in this way. Converting text to shapes is almost always desirable for print (assuming non-compatible effects aren't in use), as this will afford you the sharp vectors you want in print whilst ensuring that the printer does not require access to a potentially elusive font.
Either way, a combination of smart objects, shapes and pixels will give you some very good print options.
Hope that's of some use.