How often are aircraft flown by two FO's?
I'd say this is quite common on flights that require at least 3 pilots due to length.  The third pilot is almost assuredly going to be qualified as a first officer and this is the common staffing strategy with the US carriers that I am familiar with.

Three pilots (by US flag rules) are going to be required for 8-12 hour flights and you'll find that US carriers often will staff a third pilot even on the shorter US east coast &lt;-> western Europe flights.  But what must the three pilot composition be?  Lets examine 14 CFR 121.543 the requirement to relieve a PIC (excepted):   


  §121.543   Flight crewmembers at controls.
  (a) Except as provided in paragraph (b) of this section, each required flight crewmember on flight deck duty must remain at the assigned duty station with seat belt fastened while the aircraft is taking off or landing, and while it is en route.
  
  (b) A required flight crewmember may leave the assigned duty station—
  
  (3) If the crewmember is taking a rest period, and relief is provided—
  
  (i) In the case of the assigned pilot in command during the en route cruise portion of the flight, by a pilot who holds an airline transport pilot certificate not subject to the limitations in §61.167 of this chapter and an appropriate type rating, is currently qualified as pilot in command or second in command, and is qualified as pilot in command of that aircraft during the en route cruise portion of the flight. A second in command qualified to act as a pilot in command en route need not have completed the following pilot in command requirements: The 6-month recurrent flight training required by §121.433(c)(1)(iii); the operating experience required by §121.434; the takeoffs and landings required by §121.439; the line check required by §121.440; and the 6-month proficiency check or simulator training required by §121.441(a)(1);


The limitations of 61.167 mentioned above mean those under the age of 23 are not eligible to relieve the PIC. What does it mean to be "qualified as pilot in command of that aircraft during the en route cruise portion of the flight?"  The closest I can find to answer that is in 121.436 which says to be act as a PIC you must have an ATP and be at least 23 years old, have a type rating and have at least 1000 hours combined from part 121 SIC, part 91.1053(a)(2)(i) PIC, part 135.243(a)(1) PIC time.

What this means practically, is that a second in command who 


holds an ATP, 
is at least 23 years old,
is type rated in the airplane,
is qualified as a second in command, and
has at least 1000 hours SIC time with any airline


may relieve a PIC during en-route flight.

This is further reinforced by the remainder of the quoted portion of 121.543 that says an SIC qualified as PIC need not have any of the required checks a PIC must have (line check, 6 month sim check, etc).  

At a major airline it is likely that SIC have ATPs and are type rated during initial training and most major new-hires will be older than 23.  It is also likely they have prior airline experience to give them 1000 hours SIC.  Even if they don't have that experience, they'll have it in a 18 months or less after being hired.

This means that pretty much any FO at the airline and surely any FO who has been there for a year or two is going to be qualified to relieve a PIC.  Because an FO can relieve the PIC and can also relieve an SIC, the third pilot need only be an FO.  This means our crew of three will be one captain and two first officers.

Given the economics involved and the behavior of US airlines when it comes to costs, they will staff an FO wherever they can versus staffing a captain.  

To bring this full circle, back to our 8-12 hour flights to/from the US by US carriers that require 3 pilots they will almost always be flown by two first officers during the en-route portion of the flight.   



I'm not familiar with non-US regs, so this might not apply.  Given that air carrier rules by the FAA are compatible with ICAO though, I'd guess that this is the common case in other jurisdictions as well.