Yes, I know about ARP but that relies somewhat on IP layer connectivity in that the remote system must be configured with an IP on a recognized subnet. Is there any way to just dump off what mac addresses the interface has seen Ethernet frames from; either recently or since the interface was initialized -- I'm not picky which.
I think what you need is to set your NIC under promiscuous mode there are more than a dozen tools on that page that either through filtering or directly will let you do what you want.
You might be able to do this with a kernel event tracer such as SystemTap or LTTng. SystemTap has probe::netdev.rx and LTTng has net_dev_receive, either of which should do what you want.
However, I agree with @user. Packet capture is probably your best bet.
arp -an will show what you you are looking for. There is a time out for how long the MAC will stay in the table.
It really sounds like you are asking for arpwatch: http://www.securityfocus.com/tools/142
It will keep a database and email you when it sees new MAC addresses on any interface you configure it for.