After many helpful suggestions it doesn't look like there's any way you can do this.
HDMI-CEC: This isn't enabled on the PS3 by default (confirmed in the menu system when I finally did get in) and no key on my TV remote had any impact on the PS3
USB keyboard: No keys had any effect, except the Windows key, and all this did was show a "no entry" symbol
Using the Bluray remote itself: Doesn't work as it uses Bluetooth to communicate with the PS3 and can't be paired with the PS3 until you're in the PS3's menu system (the BD remote has no mini USB port like a Dualshock controller does which presumably allows the Dualshock to communicate with the PS3 before the Bluetooth pairing happens).
In the end I borrowed a controller from a friend for all of 1 minute - all it took to complete setup, get into the PS3 menu, and pair the BD remote.