Sub Panel Install - Main Panel Full
I'll address each of your four questions in turn.


You can do this without moving any circuits by replacing the 20A tandem breaker in slots 10/12 and the 30A two-pole breaker occupying slots 14/16 and 18/20 with a 20A/30A quadruplex breaker with a center common trip which will take the circuit from the 30A breaker and independent, non-tied outer trips that take the circuits served by the 20A tandem breaker -- in your case, the Eaton BQC2302120 -- and then shifting the two 40A two-pole breakers (one is in 22/24 and 26/28, the other is in 30/32 and 34/36) on that side up a full width slot (so that you would have a quadruplex in 10/12 and 14/16, the first 40A two-pole in 18/20 and 22/24, and the second 40A two-pole in 26/28 and 30/32).  This would then leave you with slots 34/36 and 38/40 open to put your feeder breaker in, which of course must be an Eaton BR two-pole.
Your breakers in the subpanel must match the brand of the subpanel -- there's nothing in the NEC that prohibits a subpanel that's of a different make or breaker type than the main panel.  I'd recommend installing another Eaton type BR panel and matching breakers, though, simply for consistency's sake (it makes your electrician's life slightly easier when it comes to sourcing parts, and also makes the subpanel breakers behave the same as the main panel's breakers :).
Since you have 1100 ft^2 of space to cover with this wiring project, you will need to account for a minimum of 3300VA of lighting and general receptacle load; this is based on the 3 VA/ft^2 figure given by Table 220.12 (the 35% demand factor for load over 3000VA given in Table 220.42 is apparently inapplicable in a 220.83(B) calculation).  Atop this, you will be putting three 1000VA heaters, giving you another 3000VA of heating load for a total of 6300VA on the feeder, which works out to 26.25A.  While it's technically permissible to treat the heating as a continuous load and the general load as noncontinuous load and then use the 215.2(A)(1)(a) method (125% of continuous load + 100% of noncontinuous load) and use a 30A breaker and feeder, I would use a 40A breaker and appropriately oversized feeder (50A ampacity minimum) to be safe and keep voltage drops reasonable.  Don't forget to re-run the 220.83 computation for your overall service to make sure you aren't overloading it!
Since you don't need a 100A feeder (the field reports I have read about electric tankless heaters are that they are a real waste of money) and can get away with 40A minimum instead, you can use a smaller cable, all the way to 8/3 NM.  If you wish to use the 2-2-2-4 Al SE cable you linked, though (it's cheap!), you will be limited to 75A maximum due to 338.10(4)(a) in conjunction with the 60 deg C column in Table 310.15(B)(16):



  Interior Installations. In addition to the provisions of this article, 
  Type SE service-entrance cable used for interior wiring shall comply with the 
  installation requirements of Part II of Article 334, excluding 334.80.
  
  Where installed in thermal insulation the ampacity shall be in accordance with
  the 60°C (140°F) conductor temperature rating. The maximum conductor 
  temperature rating shall be permitted to be used for ampacity adjustment and 
  correction purposes, if the final derated ampacity does not exceed that for
  a 60°C (140°F) rated conductor.


Addendum: You are correct in that you can use a heavier-rated loadcenter in this application; however, Eaton does not list a 100A BR main lug loadcenter in their catalog.  I'd recommend Eaton part number BR816L125FDP for a flush mount loadcenter or a BR816L125SDP for a surface mount loadcenter -- these are 125A load centers capable of taking up to 8 full-width BR breakers or serving 16 circuits when loaded with tandem breakers and pre-equipped with main lugs to run the feeder into (otherwise, you'd need to burn two slots for a main lug kit).  You will also need a GBK10 ground bar here (Eaton makes ...FGDP/SDGP versions with the ground bar preinstalled, but the blue box doesn't carry them).