You can partition an existing table. Not by adding partitions to it, but by rebuilding the clustered index onto a partition scheme. This will take as long as rebuilding the clustered index usually takes, it won't be instant.
Once partitioned, you can switch out a partition of data (swap a partition with an empty table) to do fast 'deletes'
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability