(Note: we also have a blog post on this topic, it's dated, but remains relevant: http://www.webperformance.com/load-testing/blog/2011/07/modifying-recorded-urls-in-load-tester-4-2/)
One way:
(1) In the testcase editor, choose the "Entire Testcase" root node of the testcase.
(2) Choose the Fields View (one of the tabbed views usually located in the lower half of the window).
(3) Choose the "hostnames" specialization, instead of the default "-- Table Default --" specialization.
(4) Now, the Fields View will show a hostname for every request in your testcase. Shift-select or ctrl-select the hostnames that you want to edit. Fields that are highlighted in a color other than plain white already have a datasource assigned to them. Those fields will trigger a warning about the conflicting assignment as you work through the next step. You might want to leave those fields alone.
(5) Right-click on the selections and choose "Edit..." to bring up the datasource editor. This editor will let you assign a datasource to every field simultaneously.
Another way:
(1) In the Testcase Editor, choose Options > View > URL Editor.
(2) In the "Datasource" column, you can edit the base URL for any sub-tree.
(3) If you have a problem with conflicted fields, consider using the first technique above, as you can select around the conflicts.