Yes it is possible.
You need different SSID's and maintain 2 channel separation between all AP's with overlapping coverage area be they yours or the other companies AP's
I would also add steps to ensure that the clients from the other company can NOT associate to your AP's
LEAP/EAP is the best option for this but it can be done with MAC address filters combined with static WEP and tweaks such as turning off broadcast SSID
I recommend that you read the SAFE whitepaper for full details on this
http://www.cisco.com/en/US/products/hw/wireless/ps458/products_white_paper09186a00800b469f.shtml