How big do you want your picklist to be? 

The way I accomplished this is that I made a custom object and put all the possible Lookup Values as part of this Custom Object.  Then I build a selectoption list in Visualforce and Apex itself.  It may not be exactly what you're looking for but it might point you in the right direction.

VF:

<!-- This builds a picklist from a custom object, along with getItems in the controller --> 
        <apex:selectList value="{!countries}" size="1" multiselect="false">
            <apex:selectOptions value="{!items}"/>
        </apex:selectList><p/>

Now in the Controller I'm using getItems, which is what's referenced from SelectOptions

Edit: Forgot an important step.  The getters and setters for the custom object in question have to be written in the Apex code.  In this example the selectlist value = countries, so in my Apex Code we instantiate the following:

public String countries;
public String getCountries() { return countries; }
    public void setCountries(String countries) { this.countries = countries; }

Apex:

public List<SelectOption> getItems() 
    {
        //Let's build the list from the object.  
        //This list will not be in any order.
        List<SelectOption> options = new List<SelectOption>();
        //This takes ALL RECORDS from the Custom Object in question.  
        List<DSM_Xref__c> d = [select Name from Custom_Object];
        for(Integer i = 0; i < d.size();i++){ options.add(new selectOption(d[i].Name,d[i].Name)); }    
        
        //Now let's sort the list we just built.     
        options = SortOptionList(options);
        
        //Now this is for adding that elusive '--None--' field in.  Seems silly to build a whole new list
        //But the sort will put it on the bottom.  
        List<SelectOption> returnOptions = new List<SelectOption>();
        returnOptions.add (new selectOption('','--None--'));
        for(Integer j = 0; j < options.size(); j++)
        {
            returnOptions.add (options[j]);
        }
        return returnOptions;
    }

And to sort the List, we have a SortOptionList.  Since the Records in the custom field are pulled from the Database, they won't necessarily be in the same order as you put them in.  So if you're looking for alphabetical order, use the following simple sort:

public static List<SelectOption> SortOptionList(List<SelectOption> ListToSort)  
    {       
        if(ListToSort == null || ListToSort.size() <= 1){ return ListToSort; }                  
       
        List<SelectOption> Less = new List<SelectOption>();     
        List<SelectOption> Greater = new List<SelectOption>();      
       
        integer pivot = 0;              
        // Save the pivot and remove it from the list       
        SelectOption pivotValue = ListToSort[pivot];        
        ListToSort.remove(pivot);               
       
        for(SelectOption x : ListToSort)        
        {           
            if(x.getLabel() <= pivotValue.getLabel()) { Less.add(x); }            
            else if(x.getLabel() > pivotValue.getLabel()) { Greater.add(x); }            
        }       
       
        List<SelectOption> returnList = new List<SelectOption> ();      
        returnList.addAll(SortOptionList(Less));        
        returnList.add(pivotValue);     
        returnList.addAll(SortOptionList(Greater));     
        return returnList;  
    }

Like I said it might not be EXACTLY what you're looking for, but this will build a picklist from the Lookup Relationship.  There are size requirements to a picklist that I don't know off the top of my head, but if you try and have a very large picklist you might run into that limit.  

Hope this helps.

Also, note that there have been small changes to the code, so this won't copy-and-compile.  Just an FYI.