Specifying prerequisites for Puppet custom facts

I have written a custom Puppet fact that requires the biosdevname tool to be installed. I'm not sure how to set things up correctly such that this tool will be installed before facter tries to instantiate the custom fact.

Facts are loaded early on in the process, so I can't simply put a package { biosdevname: ensure => installed } in the manifest, since by the time Puppet gets this far the custom fact has already failed.

I was curious if I could resolve this through Puppet's run stages. I tried:

stage { pre: before => Stage[main] }
class { biosdevname: stage => pre }

And:

class biosdevname {
  package { biosdevname: ensure => installed }
}

But this doesn't work…Puppet loads facts before entering the pre stage:

info: Loading facts in physical_network_config
./physical_network_config.rb:33: command not found: biosdevname -i eth0
info: Applying configuration version '1320248045'
notice: /Stage[pre]/Biosdevname/Package[biosdevname]/ensure: created

Etc. Is there any way to make this work?

EDIT: I should make it clear that I understand, given a suitable package declaration, that the fact will run correctly on subsequent runs. The difficulty here is that this is part of our initial configuration process. We're running Puppet out of kickstart and want the network configuration to be in place before the first reboot.

It sounds like the only workable solution is to simply run Puppet twice during the initial system configuration, which will ensure that the necessary packages are in place.

Also, for Zoredache:

# This produces a fact called physical_network_config that describes
# the number of NICs available on the motherboard, on PCI bus 1, and on
# PCI bus 2.  The fact value is of the form <x>-<y>-<z>, where <x>
# is the number of embedded interfaces, <y> is the number of interfaces
# on PCI bus 1, and <z> is the number of interfaces on PCI bus 2.

em = 0
pci1 = 0
pci2 = 0

Dir['/sys/class/net/*'].each {
    |file| devname=File.basename(file)
    biosname=%x[biosdevname -i #{devname}]
    case 
    when biosname.match('^pci1')
        pci1 += 1
    when biosname.match('^pci2')
        pci2 += 1
    when biosname.match('^em[0-9]')
        em += 1
    end
}

Facter.add(:physical_network_config) do
    setcode do
        "#{em}-#{pci1}-#{pci2}"
    end
end