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'