I want to provide a screen for users to add some information about contacts (including custom info). Some of the contacts will be existing contacts, but some will be new. An autocomplete box would be ideal, similar to that used for creating a new contribution. It doesn't appear that this is possible for profiles. Can it be done with Webform-CiviCRM? I am using Drupal.
Yes, it can be done with webforms. Select a 2nd contact in the CiviCRM tab, check Existing Contact and add any other fields that you want to expose on the form (including the custom info). Click Save Settings.
Go to the Webform tab and click on the field that was created for the Existing Contact. There you can set the autocomplete option for the Form Widget (in the Display area):
Take note of the permissions setting in the Filters area as well so you don't end up exposing a lot of personal information unintentionally.